HDU 5514 Frogs（巧妙地容斥）（数论）

╰半夏微凉° 2022-07-16 03:15 111阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5514

题目大意：有n个青蛙和m个石头编号为1-m-1，青蛙每次跳Ni步，问每次跳完后覆盖的石头的编号的和是多少

解题思路：XJB推导一下能知道对于每个Ni，覆盖石头的编号为每个gcd（Ni，m）的倍数，但是如果有2，3，6，12的倍数，那么该如容斥掉呢，首先找出m的所有因子，每一个因子会对应一个贡献，将会被计算到的所有因子标记为1，然后开始枚举每一个因子，首先加上这个因子的贡献，再对后面每一个能整除它的因子贡献减去当前的贡献值，循环一遍即可，详情见代码。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <set>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int yinshu[100005];
    
    int vis[100005];
    int num[100005];
    
    int n,m;
    int main()
    {
        int T,cas=1;
        RI(T);
        while(T--)
        {
            RII(n,m);
            int len=0;
            int x=floor(sqrt(m)+0.5);
            for(int i=1; i<=x; i++)
            {
                if(m%i==0)
                {
                    yinshu[len++]=i;
                    if(m/i!=i) yinshu[len++]=m/i;
                }
            }
            sort(yinshu,yinshu+len);
            memset(vis,0,sizeof(vis));
            memset(num,0,sizeof(num));
            for(int i=1; i<=n; i++)
            {
                int x;
                RI(x);
                int gcd=__gcd(x,m);
                for(int j=0; j<len-1; j++)
                {
                    if(yinshu[j]%gcd==0) vis[j]=1;
                }
            }
            LL ans=0;
            for(int i=0; i<len-1; i++)
            {
                if(vis[i]-num[i]!=0)
                {
                    int t=(m-1)/yinshu[i];
                    ans+=(LL)(1+t)*t*yinshu[i]/2*(vis[i]-num[i]);
                    int x=vis[i]-num[i];
                    for(int j=i+1; j<len-1; j++)
                        if(yinshu[j]%yinshu[i]==0)
                        {
                            num[j]+=x;
                        }
                }
            }
    
            printf("Case #%d: %I64d\n",cas++,ans);
        }
        return 0;
    }