http://acm.hdu.edu.cn/showproblem.php?pid=5514

沒有想到怎么利用gcd的性質來改進指數級別的容斥，還是沒有理解容斥的思想，只知道基礎的。

已經知道結果就在因數之中，只要計算因數可以算幾次就可以了。

代碼：

#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 10005; int yinshu[maxn]; int a[maxn]; int gcd(int a,int b){return b==0?a:gcd(b,a%b); } int used[maxn],vis[maxn]; int main() {int t,i,j;int n,m;scanf("%d",&t);int icase=0;while(t--){memset(used,0,sizeof(used));memset(vis,0,sizeof(vis));scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)a[i]=gcd(a[i],m);int cnt=0;for(i=1;i*i<=m;i++){if(m%i==0){yinshu[cnt++]=i;if(i*i!=m)yinshu[cnt++]=m/i;}}sort(yinshu,yinshu+cnt);sort(a,a+n);for(i=0;i<cnt;i++){for(j=0;j<n;j++)if(yinshu[i]%a[j]==0){vis[i]=1;break;}} ll ans=0;for(i=0;i<cnt;i++){if((vis[i]-used[i])==0)continue;ll tmp=(m-1)/yinshu[i];ans+=(tmp+1)*tmp/2*yinshu[i]*(vis[i]-used[i]);for(j=i+1;j<cnt;j++){if(yinshu[j]%yinshu[i])continue;used[j]+=vis[i]-used[i];}}printf("Case #%d: %lld\n",++icase,ans);}// cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的HDU 5514 Frogs 容斥的全部內容，希望文章能夠幫你解決所遇到的問題。

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