沈阳 Frogs
题目链接：http://acm./showproblem.php?pid=5514
这道题目是一个典型的容斥定理类题目，通过巧妙的运用gcd可以获取青蛙的真实无限步骤后的最小步长。例如12个石子围成一圈，青蛙每次跳10步相当于
石子编号 0 1 2 3 4 5 6 7 8 9 10 11
第i步位置6 0 5 0 4 0 3 0 2 0 1(7) 0
那么他与实际每次只跳gcd（12,10）效果是一样的。
下面我们考虑m是1e9范围存不下，就只能用容斥定理进行解题。对于每一只青蛙，可以在O(1)时间内计算到达石子编号之和，但会产生两只青蛙都跳过同一个点的情况。这样再减去就可以了。当时做的时候调了半天，最后发现其实不管加还是减其实都一定是m的约数，因为是用gcd算出来的。同时这道题目算哪些点访问过只开一个数组会有些力不从心，当时调很久都没能调出来。
看了别人的才明白过来，其实只需要开两个数组对应visit数组（c）和num数组（d）每次算visit-num就是当前因子应该加减的遍数，由于算了当前的那么对于后面每一个可以被当前因子整除的num都应当调整，让后续不再多算。比如第一个样例gcd分别是2和3，那么算2的时候回把6加进ans，算3的时候又会把6加进ans，6的visit应当是1，但num却变成2，应当减去。而4和8在算2的时候算了一遍，算3的时候没有多算，那么visit=num意味着已经正常算过，不需要重复。
我之前开一个数组不可以的原因我想是因为我没有办法区分当前数据是否应当计算，只是单纯自减无法适应多层次的调整，因为比如因数较多的时候如果有2 3 4 6 12那么在算2和3会把6和12对应多算，但在处理6的时候12多算的处理已经解决，而我却无法合适的处理（自减已经不对）。或许大家有处理的好方法，期待留言。
上面的方法是一种加多则减的方法，我又看到一种更加巧妙的方法，分享给大家。原文描述有些不好，理解花了些时间，但方法真的好，是在加的时候做处理从而直接就不会加重复。我们考虑24因数为2 3 4 6 8 12的情况，对于每一个因数i，如果因数为至少一个gcd的值的倍数那么就加上所有与m/i互质的数的i倍。
对于如果有一个gcd=4，那么就有三个因数与之成倍数4,8,12。我们计算4的时候只加上与6互质的数的4倍也就是1*4和5*4对应的4和20，计算8的时候只加上与8互质的数的8倍也就是1*8和3*8对应8和24，同理算12的时候只加上了12。这样算4的时候就不会产生重复加的情况，也就不需要再想如何去减。
我们再考虑12的因数对应2,3,4,6有若干个gcd=2，3，6的情况，对于2算了与6互质的数的两倍，也就是1*2=2,5*2=10；而3算了1*3=3,3*3=9；6算了1*6=6。这样看似6可能被算多次，实际却只算了一次。也不会因为2,3,6都是6的公因子而计算多遍，因为上面说过至少一个就计算他，同时也只会计算一遍。算互质的数也很好算计算φ(m/i)*(m/i)/2就是互质数的和，再乘以i就得到结果。下面是两种思路的实现代码。
using namespace std;#include <bits/stdc++.h>#define int long longint a[10000005];int n,m;int gcd (int a,int b){return b==0?a:gcd(b,a%b);}int oula (int n){int ans=n;for (int i=2;i*i<=n;i++){if (n%i==0){ans=ans/i*(i-1);while (n%i==0) n/=i;}}if (n!=1) ans=ans/n*(n-1);return ans;}bool check (int x){for (int i=0;i<n;i++){if (x%a[i]==0)return true;}return false;}signed main (void){int _;cin>>_;int Case=0;while (_--){cin>>n>>m;bool prime=false;int ans=0;for (int i=0;i<n;i++){int x;cin>>x;a[i]=gcd(x,m);if (a[i]==1) prime=true;}if (prime) {ans=(m-1)*m/2;}else {for (int i=2;i*i<=m;i++){if (m%i==0){if (check(i)) ans+=oula(m/i)*m/2;if (i*i!=m&&check(m/i)) ans+=oula(i)*m/2;}}}printf("Case #%d: %lld\n", ++Case, ans);}}/*本代码参考:/Cassie_zkq/article/details/101560583*/
using namespace std;#include <bits/stdc++.h>#define int long longint a[10000005];int b[10000005];int c[10000005];int d[10000005];int n,m;int gcd (int a,int b){return b==0?a:gcd(b,a%b);}signed main (void){int _;cin>>_;int Case=0;while (_--){cin>>n>>m;bool prime=false;int ans=0,cnt=0;for (int i=0;i<n;i++){cin>>a[i];if (gcd(a[i],m)==1) prime=true;}if (prime) {ans=(m-1)*m/2;}else {for (int i=2;i*i<=m;i++){if (m%i==0){b[cnt++]=i;b[cnt++]=m/i;}}sort(b,b+cnt);for (int i=0;i<n;i++){for (int j=0;j<cnt;j++){if (b[j]%gcd(a[i],m)==0){c[j]=1;}}}//for (int i=0;i<cnt;i++) cout<<c[i]<<' ';cout<<'\n'; //for (int i=0;i<cnt;i++) cout<<b[i]<<' ';cout<<'\n'; for (int j=0;j<cnt;j++){if (c[j]!=d[j]){ans+=m*(m/b[j]-1)/2*(c[j]-d[j]);//cout<<j<<'+'<<m*(m/b[j]-1)/2*(c[j]-d[j])<<'\n';for (int i=j+1;i<cnt;i++){if (b[i]%b[j]==0){d[i]+=c[j]-d[j];}}}}//for (int i=0;i<cnt;i++) cout<<d[i]<<' ';cout<<'\n'; for (int i=0;i<cnt;i++) d[i]=c[i]=b[i]=0;}printf("Case #%d: %lld\n", ++Case, ans);}}
