首页 > 代码库 > 【数论】【枚举约数】【欧拉函数】bzoj2705 [SDOI2012]Longge的问题
【数论】【枚举约数】【欧拉函数】bzoj2705 [SDOI2012]Longge的问题
∵∑gcd(i, N)(1<=i <=N)
=k1*s(f1)+k2*s(k2)+...+km*s(km) {ki是N的约数，s(ki)是满足gcd(x,N)=ki(1<=x<=N)的x的个数}
∴gcd(x,N)=ki (1<=x<=N) <=> gcd(x/ki,N/ki)=1 (1<=x/ki<=N/ki)
gcd(x/ki,N/ki)=1 (1<=x/ki<=N/ki) 的x的个数 即为φ(N/ki)
∴ans=∑φ(N/ki)*ki
∴O(sqrt(N))枚举约数即可。
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 typedef long long ll; 5 ll n,ans; 6 int phi(ll x) 7 { 8 ll res=x; 9 for(ll i=2;i*i<=x;i++)10 if(x%i==0)11 {12 res=res/i*(i-1);13 while(x%i==0) x/=i;14 }15 if(x>1) res=res/x*(x-1);16 return res;17 }18 int main()19 {20 scanf("%lld",&n);21 for(ll i=1;i*i<=n;i++) if(n%i==0) ans+=(phi(n/i)*i+phi(i)*(n/i));22 printf("%lld\n",ans);23 return 0;24 }
【数论】【枚举约数】【欧拉函数】bzoj2705 [SDOI2012]Longge的问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。