HDU 5514 Frogs ACM/ICPC 2015 Shenyang（容斥原理）

Frogs

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 2580    Accepted Submission(s): 849

Problem Description

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

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.

Sample Input

3

2 12

9 10

3 60

22 33 66

9 96

81 40 48 32 64 16 96 42 72

Sample Output

Case #1: 42

Case #2: 1170

Case #3: 1872

Source

​​2015ACM/ICPC亞洲區沈陽站-重制賽（感謝東北大學）​​

        有很多個青蛙在繞着一個圓圈跳，第i隻青蛙每次能夠跳ai步，然後起始點為0，問你把所有青蛙能夠踩到的點的位置編号加起來結果是多少。

        有了之前一道博弈題的經驗，我們很快能夠知道，如果一隻青蛙每次跳的距離是ai，那麼所有gcd(ai,m)的倍數的編号都能夠被走到。于是就相當于求所有的gcd的倍數的和。問題很快就出現了，會出現重複。

        計算倍數的和與計算倍數的個數很類似，于是很容易想到之前多校的TrickGCD那題，那題就是用莫比烏斯函數去容斥。但是這題m的範圍很大，不可能求出莫比烏斯函數，同時暴力容斥即使是O(N)的也會逾時，何況還達不到O(N)。是以說這麼做肯定是不行的。于是當時我就陷入了沉默，始終無法找到解決的方法。

        直到看了看題解……我們發現，其實我隻需要對m的所有約數進行暴力就行了，那麼這個怎麼了解呢？可以證明，這樣子做所有不是m約數的數字都隻會被計算一次。我可以簡單的證明一下，假設某個不是m約數的數字被計算了兩次，那麼一定是被兩個互質的gcd給重複計算了，又gcd都是m的約數，那麼這兩個gcd的lcm要麼大于m，要麼還是m的約數，前者顯然沖突；後者若該數字不是lcm，那必然是lcm的倍數，則會被lcm給容斥而隻計算一次。

#include<bits/stdc++.h>
#define LL long long
#define N 100010
using namespace std;

int num[N],times[N],tot,n,m;
bool vis[N];

void divide(int n)                    //求n的所有約數
{
    tot=0;
    for(int i=1;i*i<=n;i++)
    {
        if (n%i) continue;
        num[++tot]=i;
        if (i*i!=n) num[++tot]=n/i;
    }
}

int main()
{
    int T_T,T;
    cin>>T_T;T=T_T;
    while(T_T--)
    {
        LL ans=0;
        scanf("%d%d",&n,&m);
        memset(vis,0,sizeof(vis));
        memset(times,0,sizeof(times));
        divide(m); sort(num+1,num+1+tot);
        for(int i=1;i<=n;i++)
        {
            int x; scanf("%d",&x);
            int gcd=__gcd(x,m);
            for(int i=1;i<=tot;i++)
                if (num[i]%gcd==0) vis[i]=1;        //統計每個點應該做的貢獻
        }
        for(int i=1;i<=tot;i++)                //進行容斥
        {
            int d=vis[i]-times[i];
            if (vis[i]==times[i]) continue;
            ans+=(LL)(m-num[i])*(m/num[i])/2*d;        //計算貢獻，多了就減，少了就加
            for(int j=i+1;j<=tot;j++)
                if (num[j]%num[i]==0) times[j]+=d;    //容斥操作，所有倍數實際貢獻更改
        }
        printf("Case #%d: %I64d\n",T-T_T,ans);
    }
    return 0;
}