【HDOJ5514】Frogs（容斥原理）

题意：n个青蛙在一个有m个节点的圆上跳，m个节点的标号为0-m-1，每只青蛙每次跳的节点数给出，让求n只青蛙所跳位置标号之和

n<=1e4，m<=1e9，a[i]<=1e9

思路：由裴蜀定理可知该问题等价于[0,m-1]能被至少一个gcd(m,a[i])整除的数字之和

因为n过大，考虑与m的因子个数相关的算法，因子个数<=200

做因子之间的容斥，每一个因子a[i]的贡献t=贡献次数*a[i]*(m/a[i]-1)*(m/a[i])/2

后面部分是一个等差数列

算完每一个因子的贡献之后再维护其倍数因子的贡献

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 typedef long long ll;

 typedef unsigned long long ull;

 using namespace std;

 #define N   40000

 #define M   32

 #define oo  10000000

 #define MOD 105225319

 int a[N],vis[N];

 int gcd(int x,int y)

 {

     if(!y) return x;

     return gcd(y,x%y);

 }

 int main()

 {

      int cas;

      scanf("%d",&cas);

      for(int v=;v<=cas;v++)

      {

          int n,m;

          scanf("%d%d",&n,&m);

          memset(vis,,sizeof(vis));

          int tot=;

          for(int i=;i*i<=m;i++)

           if(m%i==)

           {

               a[++tot]=i;

               if(i*i!=m) a[++tot]=m/i;

           }

          sort(a+,a+tot+);

         for(int i=;i<=n;i++)

         {

             int x;

             scanf("%d",&x);

             int t=gcd(m,x);

             for(int j=;j<=tot;j++)

              if(a[j]%t==) vis[j]=;

         }

         ll ans=;

         for(int i=;i<=tot;i++)

          if(vis[i])

          {

              ll t=m/a[i];

              ans+=(ll)a[i]*t*(t-)/*vis[i];

              for(int j=i+;j<=tot;j++)

               if(a[j]%a[i]==) vis[j]-=vis[i];

          }

         printf("Case #%d: %I64d\n",v,ans);

     }

     return ;

 }

巴特西

【HDOJ5514】Frogs（容斥原理）

最新文章

热门文章