這道題之前沒有看數論函數的時候搞懂了,想到直接用歐拉函數做,現在再來看第一個想法就是這不是莫比烏斯反演嘛.
但還是能用簡單數論知識直接做出來的還是盡量做簡單一點.
兩種方法想到后都寫的差不多對了,都爆long long 了.萬惡的long long .實在是煩.切記切記,只要是乘積,或者是累加的地方都要注意!!!
用歐拉函數做的話思路是:題目要求的是數對gcd(x,y)為素數的的個數,那么對于每個素數,我們要求的是符合范圍內的gcd=1的個數(這個思路很常見,在數論函數中也是很常見的,因為我們不好直接處理gcd=k的情況,但是如果將情況轉換為互質的情況我們就有很多的工具來進行處理),此時的范圍變為1-n/k,即我們要求這個范圍內互質的數的個數,我們不妨先令x<=y,則情況就是對歐拉函數求和,一般的話答案就是求和的兩倍-1,之所以減1是因為唯一的一種x=y的情況x=y=1被算了兩次(這種特殊情況需要注意).所以我們預處理出歐拉函數的前綴和就能很快解決問題.
需要理解的是這道題可以這樣很簡單的做是有局限性的,僅僅是因為x,y的范圍是一樣的因此可以這樣分析,如果x,y的范圍不一樣就不可以.這也是一個小技巧吧,如果數對兩個數的范圍是不一樣的一般沒有辦法簡化只能踏踏實實的用數論函數解決.
還需要注意的一個技巧是如果只有一組數據,那么預處理的數據范圍最好直接是讀入的數據而不是最大的數據,這樣可以減少很多時間.
AC代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e7+5;int phi[MAXN],prime[MAXN];
ll sum[MAXN];
bool check[MAXN]; int tot;void pre(int maxn)
{tot=0; phi[1]=1;for(int i=2;i<maxn;i++){if(!check[i]){prime[tot++]=i; phi[i]=i-1;}for(int j=0;j<tot && (ll)i*prime[j]<(ll)maxn;j++){int x=prime[j]*i; check[x]=true;if(i%prime[j]) phi[x]=(prime[j]-1)*phi[i];else{phi[x]=prime[j]*phi[i];break;}}}for(int i=1;i<=maxn;i++) sum[i]=sum[i-1]+phi[i];
}int main()
{int n;scanf("%d",&n);pre(n+3);ll ans=0;for(int j=0;j<tot && prime[j]<=n;j++){ans+=2*(ll)sum[n/prime[j]]-1;}printf("%lld\n",ans);return 0;
}再看這個的話我們還是對和式進行變形,對于每個質數p我們要求的是gcd=p的個數,記為f§,我們記g(x)為x|gcd 的個數,則由莫比烏斯反演得到f(x)和g(x)的關系,再用除法分塊也能很快解決問題.同樣的要注意某些地方會爆longlong
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e7+5;int prime[MAXN],mobius[MAXN],sum[MAXN];
bool check[MAXN]; int tot;void pre(int maxn)
{ll x;tot=0; mobius[1]=sum[1]=1;for(int i=2;i<maxn;i++){if(!check[i]){prime[tot++]=i; mobius[i]=-1;}for(int j=0;j<tot && (ll)prime[j]*i<(ll)maxn;j++){x=prime[j]*i; check[x]=true;if(i%prime[j]) mobius[x]=-mobius[i];else {mobius[x]=0; break;}}sum[i]=sum[i-1]+mobius[i];}
}int n;int main()
{while(~scanf("%d",&n)){pre(n+5);ll ans=0;for(int j=0;j<tot && prime[j]<=n;j++){int t=n/prime[j];for(int l=1,r;l<=t;l=r+1){r=t/(t/l);ans+=(ll)(sum[r]-sum[l-1])*(t/l)*(t/l);//沒想到這里會爆longlong想了好久...}}printf("%lld\n",ans);}return 0;
}
