給出一個數n，求出1到n的數與n的最小公倍數的和
html
多組數據函數
理所固然推柿子
spa
原題至關於求$\sum_{i=1}^{n}\frac{i*n}{gcd(i,n)}$code
先枚舉d=gcd(i,n)，而後化簡獲得$$n*\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i[gcd(i,\frac{n}{d})==1]$$htm
至關於求1到n-1中，與n互質的數和，設y<x，若是gcd(y,x)==1，那麼gcd(x-y,x)==1，兩式的貢獻就是x了blog
因此1到n-1中，與n互質的數和爲$\frac{\phi(n)*n}{2}$，特殊的，若是n=1，則數和爲1get
那麼原式就等於$$n*\sum_{d|n且d不爲n}\frac{\frac{n}{d}*\phi(\frac{n}{d})}{2}+1$$string
再化簡獲得$$n+\frac{n}{2}\sum_{d|n且d>1}d*phi(d)$$it
這樣，這個式子就變成$O(\sqrt{n})$，可是多組數據仍會超時io
實際上咱們將n質因數分解獲得$n=\prod_{i=1}^{x}p[i]^a[i]$
由於p[i]兩兩互質，因此能夠轉化爲$$n+\prod_{i=1}^{x}\sum_{j=0}^{a[i]}\phi(p[i]^j)*p[i]^j$$
根據歐拉函數的性質能夠獲得$$n+\prod_{i=1}^{x}1+\sum_{j=1}^{a[i]}(p[i]-1)*p[i]^{2j-1}$$
再根據等比數列求和公式獲得$$n+\prod_{i=1}^{x}1+(p[i]-1)*\frac{p[i]^{2*a[i]+1}-p[i]}{p[i]^2-1}$$
$$n+\prod_{i=1}^{x}1+\frac{p[i]^{2*a[i]+1}-p[i]}{p[i]+1}$$
而後線篩素數加速質因數分解就能夠過了，記得最後處理1的狀況
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; LL Mod=1e9+7; int prime[110000],m,v[110000]; void pre(int n) { m=0; for(int i=2;i<=n;i++) { if(v[i]==0) { v[i]=i; prime[++m]=i; } for(int j=1;j<=m;j++) { if(prime[j]>n/i||prime[j]>v[i]) break; v[i*prime[j]]=prime[j]; } } } LL p_mod(LL a,LL b) { LL ans=1; while(b!=0) { if(b%2==1) ans=ans*a%Mod; a=a*a%Mod;b/=2; } return ans; } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); pre(100000); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); LL ans=1,d=n; for(int i=1;i<=m&&prime[i]<=n/prime[i];i++) { LL p=prime[i]; if(n%p==0) { LL s=0; while(n%p==0) s++,n/=p; ans=ans*(1+p*((p_mod(p,2LL*s)-1+Mod)%Mod)%Mod*p_mod(p+1,Mod-2)%Mod)%Mod; } } ans=ans*(1+(LL)(n-1)*n%Mod)%Mod; ans=(ans-1+Mod)%Mod; printf("%lld\n",(ans*d%Mod*p_mod(2LL,Mod-2)%Mod+d)%Mod); } return 0; }