Main » 2013 November 25 » 【数论】SPOJ—LCMSUM
3:11 PM 【数论】SPOJ—LCMSUM |
又是一道恶心的数论题定理：对于n(n>2)，满足≤n 且与n互质的数的和 s=n*phi(n)/2。简单证明：考虑与n不互质的数a，那么容易证明n-a也与n不互质。 也就是说，不互质的数能够组成和为n的一组。 那么去除这些数后，互质的数也是可以分成和为n的组的。 所以命题得证。 令g=gcd(i,n)sigma(lcm(i,n))==sigma(i*n/g)=sigma(i/g*n/g)*g∵lcm(i/g,n/g)=1∴sigma(i/g)=n/g*φ(n/g)/2∴sigma(i/g*n/g)*g=sigma(n/g*φ(n/g)/2*n/g)*g=sigma(d*φ(d)/2)*n (n|d)令G(n)=sigma(d*φ(d)) (n|d)Ans=n*((G(n)-1)/2+1)，线性筛预处理G |
|
|
| Total comments: 0 | |