51nod 1225 余数之和

51nod 1225 余数之和

​​= (n % 1) + (n % 2) + (n % 3) + ...... (n % n)。其中%表示Mod，也就是余数。

例如F(6) = 6 % 1 + 6 % 2 + 6 % 3 + 6 % 4 + 6 % 5 + 6 % 6 = 0 + 0 + 0 + 2 + 1 + 0 = 3。

给出n，计算F(n), 由于结果很大，输出Mod 1000000007的结果即可。 分析： 6-6/1*1

6-6/2*2

6-6/3*3

6-6/4*4

6-6/5*5

6-6/6*6

得到：

可以在

内讨论n的约数，及其对应的

局部是 i*等差数列

#include #include #include using namespace std;typedef long long LL;const LL mod=1000000007;LL power(LL a,LL p){ LL ans=1; a=a%mod; while(p){ if(p&1) ans=ans*a%mod; a=a*a%mod; p>>=1; } return ans;}int main(){ LL n; LL ni=power(2,mod-2); //欧拉定理 while(~scanf("%I64d",&n)){ LL ans=((n%mod)*(n%mod))%mod; LL len=(LL)sqrt(1.0*n); for(LL i=1;i<=len;i++){ if(i==n/i){ // ans=(ans-n+mod)%mod; LL t=n/i*i; //!! ans=((ans-t)%mod+mod)%mod; continue; } LL l_r=(n/i+n/(i+1)+1)%mod; LL num=(n/i-n/(i+1))%mod; LL temp=i*num%mod; temp=(temp*l_r%mod)*ni%mod; // 逆元处理浮点问题 temp=(temp+n/i*i%mod)%mod; ans=((ans-temp)%mod+mod)%mod; } printf("%I64d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。