Question

求问个c语言问题 解释下这题的证明过程 没看懂

设n=s*q+r,s>r,s<=q,则n%s=n%q=r,s<=√n举个例子，n为17s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17r 0 1 2 1 2 5 3 1 8 7 6 5 4 3 2 1 0除数s从17到9,余数r为从0到8,公差为1的等差数列.s:17对应1.除数s从8到6,余数r为从1到5,公差为2的等差数列.s:8对应2再往前，s:5与3对应，剩个4下面先证明一下等差数列：设1<=t<=√n,u=n/t,则s为t与u时余数相同，设为r则n-r=t*u设除数为u-1时商也为t,n-r-x=t*(u-1)则x=t.同理，除数为u-k时，x=kt.所以，除数大于√n时，会形成多个等差数列.下面求一下k的范围：设被除数为n,商为t(t<=√n)因为除数大于余数,余数为r+kt=n%t+t*k则(n-(n%t+t*k))/t>n%t+t*k.解得:k<(n/t-n%t)/(t+1)则k最大取(n/t-n%t-1)/(t+1),设为K所以从右到左第t个等差数列为:从n%t到n%t+t*K,公差为t,共K+1项.和为t*K/2+n%t.1<=t<=√n再把每个等差数列的和加起来，其结果就是n%(n/√n)+...+n/n这一步时间复杂度为O(√n)再把n%1+...+n%√n加上因为√n<=n/√n,当等于的时候,n%√n加了两次,这时需要减一下n%√n这一步时间复杂度也为O(√n)最后，两步的和即为n%1+n%2+...+n%n,然后再取个余就行了。

Answer 1

# include <stdio.h>
int  get_num(long *a);
void mod(long n);
int main(void)
{
 long arr[100];
 int count=get_num(arr); //count为计数标记
 for(int i=0;i<count;i++)
   mod(*(arr+i));
 
 return 0;
}
int  get_num(long *a)
{
 int count=0;
 while(1==scanf("%ld",a) && count<=100)
 {
   a++;
   count++;
 
 }
 
 return count;  //返回输入的数的个数 
}
void mod(long n)
{
 int sum=0;
 int i;
 for(i=1;i<=n;i++)
 sum+=n%i;
 
    printf("%d\n",sum);
}

Answer 2

哪一步不懂？

Answer 3

这是ACM？