hdu 5514 (容斥)

Frogs

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

Total Submission(s): 4602    Accepted Submission(s): 1547

Problem Description

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.

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亞洲區沈陽站-重制賽（感謝東北大學）

Recommend

wange2014   |   We have carefully selected several similar problems for you:  6447 6446 6445 6444 6443 

題目大意“：n個青蛙每次跳n步石頭的編号位0- n-1 求所有的青蛙能到達的石頭編号的和

容易發現 ax=p（mod m） 改寫ax+my=p 當p模上a和m的gcd==0的時候是有解的是以答案就是

所有gcd的倍數，因為可能有重複的可以用二進制枚舉來容斥。但是後來想如果構造出很多質數的話，

不但複雜度爆炸，精度也要爆炸。

原來的題目資料比較水，二進制枚舉水了過去。

容斥的解題思路：對答案有貢獻的gcd一定是m的因子，是以我們直接得到m的因子，然後判斷該因子能否對答案做出貢獻，

對于能做出貢獻的因子我們就按照原來的思路得到答案，但是這樣是有重複的。

比如 2 3 4 6 8 16

這裡4的倍數會被算到2次 6的倍數也會被算兩次8的倍數也會被多算兩次

是以我們可以用一個num數組記錄每個因子多算了幾次，比如算2的時候，2的所有倍數的因子都被多算了一次。。

比如 2 3 4 12 16 24

算2，3，4 的時候12 和24 的倍數都被多算了2次

是以我們在算12的時候要把多算的減去 同理如果多減的話再把多減的加回來（即把12的倍數多減的再加回來）。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include<cstring>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define sca(x) scanf("%d",&x)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define inf 0x3f3f3f3f
#define LL long long
#define N 10600
#define inf 0x3f3f3f3f

LL a[N],b[N],vis[N],num[N];
LL m;
LL  SUM(LL x)
{
    return (((x+((m-1)/x*x)))*((m-1)/x))/2;
}

int main()
{
    int t;
    cin>>t;
    int  cas=0;
    while(t--)
    {
        int n;
        scanf("%d%lld",&n,&m);
        int cnt=0,tot=0,flag=0;
        rep(i,1,n)
        {
            scanf("%lld",&a[i]);
            LL tmp=__gcd(a[i],m);
            if(tmp==1)flag=1;
            b[tot++]=__gcd(a[i],m);
        }
        for(int i=1;i*i<=m;i++)
        {
            if(m%i==0)
            {
                a[cnt++]=i;
                if(i==1||i*i==m)continue;
                a[cnt++]=m/i;
            }
        }
        printf("Case #%d: ",++cas);
        if(flag)
        {
            printf("%lld\n",SUM(1LL));
        }
        else
        {
            memset(vis,0,sizeof(vis));
            memset(num,0,sizeof(num));
            sort(a,a+cnt);
            sort(b,b+tot);
            rep(i,0,cnt-1)
            {
                rep(j,0,tot-1)
                {
                    if(a[i]%b[j]==0)
                    {
                        vis[i]=1;
                        break;
                    }
                }
            }
            LL ans=0;
            rep(i,0,cnt-1)
            {
                if(vis[i])
                {
                    ans+=SUM(a[i])*(vis[i]-num[i]);
                    rep(j,i+1,cnt-1)
                    {
                        if(a[j]%a[i]==0)
                        {
                            num[j]+=vis[i]-num[i];
                        }
                    }
                }
            }
            printf("%lld\n",ans);
        }

    }
}