您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“java怎么解決歐拉函數(shù)和莫比烏斯反演問(wèn)題”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“java怎么解決歐拉函數(shù)和莫比烏斯反演問(wèn)題”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來(lái)學(xué)習(xí)新知識(shí)吧。
題意:給定a,b,c,d,k
x屬于[1 , c],y屬于[1 , d],求滿(mǎn)足gcd(x,y)=k的對(duì)數(shù)。其中<x,y>和<y,x>算相同。
解法一:不妨設(shè)c<d,x<=y。問(wèn)題可以轉(zhuǎn)化為x屬于[1,c / k ],y屬于[1,d/k ],x和y互質(zhì)的對(duì)數(shù)。
那么假如y<=c/k,那么對(duì)數(shù)就是y從1到c/k歐拉函數(shù)的和。如果y>c/k,就只能從[ c/k+1 , d ]枚舉,然后利用容斥。詳見(jiàn)代碼:
/********************************************************* file name: hdu1695.cpp author : kereo create time: 2015年02月11日 星期三 18時(shí)08分43秒 *********************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #include<stack> #include<cmath> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int sigma_size=26; const int N=100+50; const int MAXN=100000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=1000000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair<int, int> #define mk(x,y) make_pair((x),(y)) int primecnt,factcnt; int prime[MAXN],euler[MAXN],factor[N][2]; void getprime(){ primecnt=0; memset(prime,0,sizeof(prime)); for(int i=2;i<MAXN;i++){ if(!prime[i]) prime[primecnt++]=i; for(int j=0;j<primecnt && prime[j]<=MAXN/i;j++){ prime[prime[j]*i]=1; if(i%prime[j] == 0) break; } } } void geteuler(){ memset(euler,0,sizeof(euler)); euler[1]=1; for(int i=2;i<MAXN;i++){ if(!euler[i]){ for(int j=i;j<MAXN;j+=i){ if(!euler[j]) euler[j]=j; euler[j]=euler[j]/i*(i-1); } } } } int getfactor(int x){ factcnt=0; for(int i=0;prime[i]<=x/prime[i];i++){ factor[factcnt][1]=0; if(x%prime[i] == 0){ factor[factcnt][0]=prime[i]; while(x%prime[i] == 0){ x/=prime[i]; factor[factcnt][1]++; } factcnt++; } } if(x!=1){ factor[factcnt][0]=x; factor[factcnt++][1]++; } return factcnt; } int solve(int n,int m){ int ans=0; getfactor(m); for(int i=1;i<(1<<factcnt);i++){ int cnt=0,res=1; for(int j=0;j<factcnt;j++){ if(i&(1<<j)){ cnt++; res*=factor[j][0]; } } if(cnt & 1) ans+=n/res; else ans-=n/res; } return n-ans; } int main(){ int T,kase=0; scanf("%d",&T); getprime(); geteuler(); while(T--){ printf("Case %d: ",++kase); int a,b,c,d,k; scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); if(k == 0 || k>b || k>d){ printf("0\n"); continue; } if(b>d) swap(b,d); b/=k; d/=k; ll ans=0; for(int i=1;i<=b;i++) ans+=euler[i]; for(int i=b+1;i<=d;i++) ans+=solve(b,i); printf("%I64d\n",ans); } return 0; }
解法二:莫比烏斯反演。
其中"設(shè)F(a,b,k)表示有多少組x≤a,y≤b,且Gcd(a,b)≥k"的"Gcd(a,b)>=k"應(yīng)該是k | Gcd(x,y)。
/********************************************************* file name: hdu1695.cpp author : kereo create time: 2015年02月12日 星期四 09時(shí)08分41秒 *********************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #include<stack> #include<cmath> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int sigma_size=26; const int N=100+50; const int MAXN=100000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=1000000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair<int, int> #define mk(x,y) make_pair((x),(y)) int primecnt; int vis[MAXN],mu[MAXN],prime[MAXN],sum[MAXN]; void Mobius(){ primecnt=0; memset(vis,0,sizeof(vis)); mu[1]=1; for(int i=2;i<MAXN;i++){ if(!vis[i]){ prime[primecnt++]=i; mu[i]=-1; } for(int j=0;j<primecnt && i*prime[j]<MAXN;j++){ vis[i*prime[j]]=1; if(i%prime[j]) mu[i*prime[j]]=-mu[i]; else{ mu[i*prime[j]]=0; break; } } } } ll solve(int l,int r){ ll ans=0; if(l>r) swap(l,r); int last; for(int i=1;i<=l;i=last+1){ last=min(l/(l/i),r/(r/i)); ans+=(ll)(sum[last]-sum[i-1])*(ll)(l/i)*(ll)(r/i); } return ans; } int main(){ int T,kase=0; Mobius(); sum[0]=0; for(int i=1;i<MAXN;i++) sum[i]=sum[i-1]+mu[i]; scanf("%d",&T); while(T--){ int a,b,c,d,k; printf("Case %d: ",++kase); scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); if(k == 0 || k>b || k>d){ printf("0\n"); continue; } if(b>d) swap(b,d); b/=k; d/=k; printf("%I64d\n",solve(b,d)-solve(b,b)/2); } return 0; }
讀到這里,這篇“java怎么解決歐拉函數(shù)和莫比烏斯反演問(wèn)題”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì),如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。