题目链接：Frogs
题意：有n只青蛙和m块石头(石头编号为0 - n-1)排成一个环，刚开始每只青蛙都在标号为0的石头上。每只青蛙每次跳a[i]的距离，但凡被青蛙经过的石头都会被占领，求这m块石头中所有被占领过的石头的编号和。
题解：首先，可以发现每只青蛙跳过的石头的标号是gcd(a[i] , M)的倍数。所以把每只青蛙的gcd求出来后就是一个容斥了，容斥主要看代码领悟。如果出现了一个x = gcd(ai,m)，那么所有x的倍数的因数都算是出现过了，在计算的时候如果把x的倍数都加了k遍，那么就要把pk的倍数减去k遍。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define fi first 4 #define se second 5 typedef long long LL; 6 typedef pair<LL,int> P; 7 const int MAX_N = 1e5+7; 8 const LL inf = 0x3f3f3f3f3f3f3f3f; 9 LL N,M,T,S;10 int vis[MAX_N];11 LL pi[MAX_N];12 int num;13 LL gcd(LL a,LL b){14return b == 0?a : gcd(b,a%b);15 }16 void init(){17num = 0;18pi[num ++ ] = 1;19for(int i=2;i*i<=M;i++){20 if(M%i == 0){21 if(i == M/i){22 pi[num++] = i;23 }24 else{25 pi[num++] = i;26 pi[num++] = M/i;27 }28 }29}30sort(pi,pi+num);31memset(vis,0,sizeof(vis));32 }33 int main(){34cin>>T;35int out = 0;36while(T--){37 out ++;38 scanf("%lld%lld",&N,&M);39 init();40 for(int i=0;i<N;i++){41 LL t;42 scanf("%lld",&t);43 LL x = gcd(t,M);44 for(int j=0;j<num;j++){45 if(pi[j]%x == 0){46 vis[j] = 1;47 }48 }49 }50 51 LL ans = 0;52 for(int i=0;i<num;i++){53 if(vis[i] != 0){54 LL t = pi[i];55 LL n = (M-1) / t;56 ans += (t+n*t)*n/2*vis[i];57 for(int j = i+1;j<num;j++)58 {59 if(pi[j] % pi[i] == 0){60vis[j] -= vis[i];61 }62 63 }64 65 }66 }67 printf("Case #%d: %lld\n",out,ans);68}69return 0;70 }
