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