題意：將n個糖果插入f-1個擋板分成f分(a1,a2,a3...af)。

問有多少種分法能夠使得gcd(a1,a2,a3...af)=1;

解法。莫比烏斯容斥，首先按1為單位分，這時候有C(n-1,f-1)種，然后去掉gcd不是1的。這時候就規定質因子個數是奇數的就減(mou值為-1)，偶數的為加(mou值是+1)，然后出現平方數為約數的數mou值為0。這樣就做到了容斥，非常巧妙。

容斥時，要注意僅僅用計算是n的約數的數，由于假設不是n的約數，那么gcd里一定不會出現這個因子。

代碼：

/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std;#define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const int INF=1000000007;int mou[Max]; LL fac[Max]; map<pair<int,int>,LL> maps; int n,f; LL pow(LL a,int b) {LL ans=1;while(b){if(b&1)ans=(ans*a)%INF;a=(a*a)%INF;b>>=1;}return ans; } LL getreverse(LL lo) {return pow(lo,INF-2); } void init() {for(LL i=2; i<Max; i++)if(!mou[i]){mou[i]=i;for(LL j=i*i; j<Max; j+=i)mou[j]=i;// cout<<i<<" ";}mou[1]=1;for(int i=2; i<Max; i++){if((i/mou[i])%mou[i]==0) mou[i]=0;else mou[i]=-mou[i/mou[i]];}fac[0]=1;for(int i=1; i<Max; i++)fac[i]=(fac[i-1]*i)%INF; } LL C(int a,int b) {LL ans=fac[a];ans=(ans*getreverse(fac[a-b])%INF*getreverse(fac[b]))%INF;return ans; } int main() {int t;cin>>t;init();while(t--){scanf("%d%d",&n,&f);if(maps.find(pair<int,int>(n,f))!=maps.end()){printf("%I64d\n",maps[pair<int,int>(n,f)]);continue;}LL ans=0;for(int i=1; i<=n/f; i++){if((n%i)!=0)continue;ans+=C(n/i-1,f-1)*mou[i];if(ans>=INF)ans-=INF;if(ans<0)ans+=INF;}printf("%I64d\n",ans);maps[pair<int,int>(n,f)]=ans;}return 0; }

轉載于:https://www.cnblogs.com/ldxsuanfa/p/10589070.html

總結

以上是生活随笔為你收集整理的CF(439E - Devu and Birthday Celebration)莫比乌斯容斥的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。