题意： 有 n 只青蛙，一开始都在 0 点。有一堆围成一圈的石子，石子的编号是从 0 ~ (m-1)。 所有青蛙只能顺时针跳，每个青蛙可以一次跳a[i]格。问这些青蛙踩过的石子的编号总和是多少？

tags：  容斥经典题。

对 m 分解因子，对每个因子求贡献。

#include
     
      using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 200005;int T, n, m, pp[N], f[N], cnt;ll  ans;void get_pp(int mn){    cnt=0;    for(int i=1; i<=sqrt(mn); ++i)        if(mn%i==0)        {            pp[++cnt]=i;            if(mn/i != i) pp[++cnt]=mn/i;        }    sort(pp+1, pp+1+cnt);    --cnt;}void Init(){    mes(f, 0);    ans = 0;}int main(){    scanf("%d", &T);    rep(cas, 1, T)    {        scanf("%d%d", &n, &m);        Init();        get_pp(m);        int ai, tmp;        rep(i,1,n)        {            scanf("%d", &ai);            tmp = __gcd(ai, m);            rep(j,1,cnt)                if(pp[j]%tmp==0)                    f[j] = 1;        }        ll  tmp1;        rep(i,1,cnt)            if(f[i])            {                tmp1 = (m-1)/pp[i];                ans += tmp1*(tmp1+1)/2 * pp[i] * f[i];                rep(j,i+1,cnt)                    if(pp[j]%pp[i]==0)                        f[j] -= f[i];            }        printf("Case #%d: %lld\n", cas, ans);    }    return 0;}