python求余数和

happy886rr

　　某道ACM题，N为一万亿，%号表示取余数：计算N%1+N%2+N%3+...+N%N =？
　　实际上就是求  N除以1  一直到  N除以N  的余数的和，只是N数字太大了，常规for循环一万亿次需要几十小时时间，显然是算法题，原理过于简单，不解释了，直接上代码。

1. # Python求N%1到N%N的和
   
2. N=10**12;S=0;M=int(N**0.5)
   
3. for i in range(1,M+1):n=N//i-N//(i+1);a=N%(N//(i+1)+1);S+=n*a-n*(n-1)*i/2
   
4. for i in range(1,M+1):S+=N%i
   
5. print(int(S))

复制代码

　　C语言更快只需0.01秒