Board logo

标题: [原创代码] python求余数和 [打印本页]
作者: happy886rr    时间: 2016-4-27 12:45     标题: python求余数和

　　某道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秒



欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2