發(fā)現(xiàn)對(duì)于gcd問(wèn)題要多和歐拉函數(shù)聯(lián)系在一起，雖然有時(shí)候并不是互質(zhì)，但是我們知道有多少互質(zhì)的然后根據(jù)互質(zhì)的數(shù)目就能解決很多個(gè)gcd的問(wèn)題

對(duì)于這道題目，題目要求的是所有數(shù)對(duì)的gcd的和，直接思考的話有難度。但是我們?nèi)绻?lián)想到歐拉函數(shù)問(wèn)題就解決了許多。

我們對(duì)于每個(gè)數(shù)都考慮他的歐拉函數(shù)值，即有phi[x]個(gè)數(shù)和x互質(zhì)，設(shè)gcd(x,i)=1,那么gcd(tx,ti)=t，因?yàn)槲覀兛紤]的是所有互質(zhì)的數(shù)，所以可以證明每對(duì)數(shù)都會(huì)被訪問(wèn)一次且只會(huì)訪問(wèn)一次。

所以我們要做的就是得到歐拉函數(shù)值，然后對(duì)于每個(gè)數(shù)字x,和tx的最大公約數(shù)為t的數(shù)目肯定也只有phi[x]個(gè)，那么關(guān)于x的所有的gcd和就是(1+2+…+t)*phi[i]，求和就可以了

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<cmath> #include<ctime> #include<climits> #include<queue> #include<vector> #include<set> #include<map> using namespace std;typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=4e6+5;int n; int phi[MAXN]; int prime[MAXN]; bool check[MAXN]; int tot;void creat_phi() {tot=0;phi[1]=1;for(int i=2;i<MAXN;i++){if(!check[i]){phi[i]=i-1;prime[tot++]=i;}for(int j=0;j<tot && prime[j]*i<MAXN;j++){check[i*prime[j]]=true;if(i%prime[j]){phi[i*prime[j]]=(prime[j]-1)*phi[i];}else{phi[i*prime[j]]=prime[j]*phi[i];break;}}} }int main() {creat_phi();ll ans,t;while(~scanf("%d",&n) && n){ans=0;for(int i=2;i<=n;i++){t=n/i;ans+=t*(t+1)/2*phi[i];}printf("%lld\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的UVa11426——欧拉函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。