HDU 5514 Frogs （容斥定理）

本文主要是介绍HDU 5514 Frogs （容斥定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有n个青蛙在由m个石头组成的圆圈上跳。告诉你每个青蛙每次跳的步长，计算所有被青蛙跳过的石头的编号和。
解法：http://www.cnblogs.com/qscqesze/p/4933949.html

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define X first
#define Y second
#define cl(a,b) memset(a,b,sizeof(a))typedef pair<int,int> P;
const int maxn=100005;
const LL inf=1<<27;
int f[maxn],g[maxn];
int p[maxn];
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);
}
int main(){int T,cas=1;scanf("%d",&T);while(T--){LL n,m;scanf("%lld%lld",&n,&m);int cnt=0;for(int i=1;i*i<=m;i++){if(m%i==0){p[cnt++]=i;if(m/i!=i)p[cnt++]=m/i;}}sort(p,p+cnt);cl(f,0);cl(g,0);for(int i=0;i<n;i++){LL x;scanf("%lld",&x);LL t=gcd(x,m);for(int j=0;j<cnt;j++)if(p[j]%t==0){f[j]=1;}}f[cnt-1]=0;LL ans=0;for(int i=0;i<cnt;i++){if(f[i]!=g[i]){LL t=(m-1)/p[i];ans+=t*(t+1)/2*p[i]*(f[i]-g[i]);t=f[i]-g[i];for(int j=i;j<cnt;j++){if(p[j]%p[i]==0){g[j]+=t;}}}}printf("Case #%d: %lld\n",cas++,ans);}return 0;
}

这篇关于HDU 5514 Frogs （容斥定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---