HDU 5514 Frogs (容斥思想+數論知識)*

Frogs Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 4142    Accepted Submission(s): 1396 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:  6437 6436 6435 6434 6433

#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;

#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)

#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
/*
題目大意:n個青蛙，每個青蛙在一個0~m-1的環上，
從0出發，每個都有步數，要求開所有能被青蛙踩到的環下标和。

可以知道x=gcd(x,m)（模拟一下就可以感受到）
一開始用最普通的容斥做，dfs容斥，
就是隻保留最小的因子（不一定是質數），
然後利用這些來進行容斥，光榮逾時/。。。。。

最後還是采用了貢獻的思想，
一旦有個因子能被青蛙走到，其倍數的貢獻都加一，

在後面周遊計算時，如果該枚舉的因子貢獻不為零，則計算它的貢獻值（要乘上其vis值，可能為負），
然後對于它的倍數減去它的貢獻，
這樣配合篩法進行容斥（我感覺篩法就是數論中的Dp精髓）。

可以看到vis數組的值變化在-1，0和1區間内。
并且該算法對每個因子維護的vis數組其實就是它的重複度，
本質上，比如有個數x,被前面的因子篩了s次，那麼判别到它時肯定要減去它的重複度，
因為被篩了肯定也被初始化為1，是以重複度為s-1，減去後，後面的倍數也被更新，
被更新為0，因為前面因子的出現導緻後面的倍數無影響或影響被覆寫，符合題目精髓。。。

*/

const int  maxn =2e4+5;
const int mod=1e9+7;
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}

int n,m,x;
int yinzi[maxn],tot=0;
int vis[maxn];
///容斥的過程

int main()
{
    int t;scanf("%d",&t);
    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d%d",&n,&m);

        tot=0;yinzi[tot++]=1;///注意篩選因子的時候要加上1
        for(int i=2;i*i<=m;i++)
        {
            if(m%i==0)
            {
                if(i*i==m) yinzi[tot++]=i;
                else
                {
                    yinzi[tot++]=m/i;
                    yinzi[tot++]=i;
                }
            }
        }

        sort(yinzi,yinzi+tot);
        memset(vis,0,sizeof(vis));

        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            x=gcd(x,m);///青蛙的步伐
            for(int j=0;j<tot;j++)   if(yinzi[j]%x==0) vis[j]=1;///初始化所有步數的倍數都要有貢獻
        }

        ll ans=0;
        for(int i=0;i<tot;i++)
        {
            if(vis[i])
            {
                ll tp=m/yinzi[i];
                ans+=1LL*yinzi[i]*(tp-1)*tp/2*vis[i];
                for(int j=i+1;j<tot;j++)
                {
                    if(yinzi[j]%yinzi[i]==0)
                        vis[j]-=vis[i];///計算過的就不用計算了,減去它的貢獻，另一類容斥
                }
            }
        }

        printf("Case #%d: %lld\n",ca,ans);
    }
    return 0;
}