题意： n只青蛙，m个石头，青蛙从1 ~ n 编号，石头从0 ~ m-1 编号，石头围成一个圆圈，每只青蛙可以跳a[i]步，即当这只青蛙在编号j的石头上时，它可以跳到 (j+a[i])%m的石头上，问你有哪些石头被青蛙踩过，只需要输出石头编号之和。
思路： 显然，距离为a[i]的青蛙可以走到的石头是小于m的g=gcd(a[i],m)倍数（不包括m，因为没有编号为m的石头 ），那我们对于g，它产生的贡献是（g+m-g）*(m/g-1)/2，那么问题来了，被重复计算的怎么减掉呢？我们可以先对m进行分解因子，然后对于每个g，枚举m的因子，如果有因子是它的倍数，那么这个因子应该被计算，把cnt[j]置为1，cnt表示这个因子应该被计算多少次，最后再枚举因子，计算贡献，计算了这个数字的因子，就把这个因子的倍数的need修改，need表示这个因子被计算了多少次。
#include<bits/stdc++.h> #pragma GCC optimize("Ofast") #define endl '\n' #define null NULL #define ls p<<1 #define rs p<<1|1 #define fi first #define se second #define mp make_pair #define pb push_back #define ll long long #define int long long #define pii pair<int,int> #define ull unsigned long long #define all(x) x.begin(),x.end() #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; char *fs,*ft,buf[1<<20]; #define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++; inline int read(){int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();} return x*f;} using namespace std; const int N=1e5+5; const int inf=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-7; const double PI=acos(-1); int a[N],cnt[N],need[N]; signed main() { int t; cin>>t; for(int Case=1;Case<=t;Case++) { int n,m; cin>>n>>m; vector<int>v; memset(cnt,0,sizeof cnt); memset(need,0,sizeof need); for(int i=1;i*i<=m;i++) { if(m%i==0) { v.pb(i); if(i*i!=m&&i!=1) v.pb(m/i); } } sort(all(v)); for(int i=1;i<=n;i++) { cin>>a[i]; int g=__gcd(a[i],m); for(int j=0;j<v.size();j++) if(v[j]%g==0) cnt[j]=1; } int res=0; for(int i=0;i<v.size();i++) { res+=m*(m/v[i]-1)/2*(cnt[i]-need[i]); for(int j=i+1;j<v.size();j++) if(v[j]%v[i]==0) need[j]+=cnt[i]-need[i]; } printf("Case #%lld: %lld\n",Case,res); } }