首页 > 代码库 > BZOJ 2226 Spoj 5971 LCMSum 数论
BZOJ 2226 Spoj 5971 LCMSum 数论
题目大意:给定n,求LCM(1,n)+LCM(2,n)+...+LCM(n,n)
枚举d=GCD(i,n),令F(n)为n以内与n互质的数之和
则ans=Σ[d|n]d*F(d)*n/d=nΣF(d)
现在就是F(n)的问题了 我们发现对于任意n>=3,如果x与n互质,那么n-x一定与n互质
故n以内与n互质的数能两两凑成和为n的数对,一共φ(n)/2对,故F(n)=n*φ(n)/2
注意n<=2时不满足上述条件,但是2满足上面那个式子,1就特判吧。。。
时间复杂度O(T√n) 很疑惑这种复杂度为何在SPOJ能卡过去。。。。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1001001 using namespace std; int phi[M],prime[M],tot; bool not_prime[M]; void Linear_Shaker() { int i,j; phi[1]=1; for(i=2;i<M;i++) { if(!not_prime[i]) { prime[++tot]=i; phi[i]=i-1; } for(j=1;i*prime[j]<M;j++) { not_prime[prime[j]*i]=1; if(i%prime[j]==0) { phi[prime[j]*i]=phi[i]*prime[j]; break; } phi[prime[j]*i]=phi[i]*(prime[j]-1); } } } long long F(int n) { if(n==1) return 1ll; return (long long)n*phi[n]>>1; } long long Calcualte(int n) { int i; long long re=0; for(i=1;i*i<n;i++) if(n%i==0) re+=F(i),re+=F(n/i); if(i*i==n) re+=F(i); return re; } int main() { int T,n; Linear_Shaker(); for(cin>>T;T;T--) { scanf("%d",&n); printf("%lld\n",Calcualte(n)*n ); } }
BZOJ 2226 Spoj 5971 LCMSum 数论
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。