HDU 5514(哈？)

There are m stones lying on a circle, and n frogs are jumping over them. The stones are numbered from 0 to m−1 and the frogs are numbered from 1 to n . The i -th frog can jump over exactly ai stones in a single step, which means from stone j mod m to stone (j+ai) mod m (since all stones lie on a circle). All frogs start their jump at stone 0 , then each of them can jump as many steps as he wants. A frog will occupy a stone when he reach it, and he will keep jumping to occupy as much stones as possible. A stone is still considered ``occupied" after a frog jumped away. They would like to know which stones can be occupied by at least one of them. Since there may be too many stones, the frogs only want to know the sum of those stones' identifiers. Input

There are multiple test cases (no more than 20 ), and the first line contains an integer t , meaning the total number of test cases.

For each test case, the first line contains two positive integer n and m - the number of frogs and stones respectively (1≤n≤104, 1≤m≤109) . The second line contains n integers a1,a2,⋯,an , where ai denotes step length of the i -th frog (1≤ai≤109) . Output For each test case, you should print first the identifier of the test case and then the sum of all occupied stones' identifiers.

这个题我上网查到一个规律（原谅我实在蠢，这个也要上网查），就是第i个ha他能跳到的石头是gcd(a[i],m)，根据这个，我们可以很愉快的 把m的因子提取出来，然后记录a[i]与m的gcd，根据这些将ha们能跳到的地方标记上1（数组b），然后容斥，那个数组c是用来记录每个因子在之前被计算了多少次的（大概这样），最后一个循环不懂的建议手写一遍各位大佬应该就懂了（不像本弱鸡，手写了还是懵逼）

#include <iostream> #include <algorithm> #include <vector> #include <stack> #include <string.h> #include <cstdio> #include <map> #include <queue> #include <math.h> #include <cstring> #include <set> #define fi first #define se second #define INF 0x3f3f3f3f using namespace std; typedef long long LL; const LL MOD=1e9+7; const double eps=1e-9; LL gcd(LL x,LL y) { if(y==0)return x; else return gcd(y,x%y); } LL n,m,a[10000+233],b[10000+233],c[10000+233]; LL tot; int main() { int T; scanf("%d",&T); LL cas=0; while(T--) { tot=0; scanf("%lld%lld",&n,&m); for(int i=1;i*i<=m;i++) { if(m%i==0) { a[++tot]=i; LL x=m/i; if(x>i)a[++tot]=x; } } sort(a+1,a+tot+1); //if(a[tot]==m)tot--; memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=0;i<n;i++) { LL x; scanf("%lld",&x); x=gcd(x,m); for(int j=1;j<=tot;j++) { if(a[j]%x==0) { b[j]=1; } } } b[tot]=0; LL ans=0; for(int i=1;i<=tot;i++) { if(c[i]!=b[i]) { LL x; x=m/a[i]; ans+=(x-1)*x/2*a[i]*(b[i]-c[i]); x=b[i]-c[i]; for(int j=i;j<=tot;j++) { if(a[j]%a[i]==0)c[j]+=x; } } } printf("Case #%lld: ",++cas); printf("%lld\n",ans); } return 0; }