HDU5514 Frogs

題目：

給n個青蛙，每個青蛙每次跳ai步

給一串循環的石頭，編号從0~n-1

求所有被青蛙踩過的石頭的編号和

分析：

很容易得到，第i個青蛙跳的石頭編号都是gcd(ai,m)的倍數

但m與n很大，接下來不能簡單模拟

另g=gcd(ai,m)

第i個青蛙貢獻的編号和為sum=∑k*g ,k=1,2,3,…[m/g]

=(1+2+3+…..+[m/g])*g

=[m/g]*([m/g]+1)/2 *g

（利用1+2+3+…+n的求和公式）

于是我們用公式可以O（1）求出每個青蛙的貢獻，但是這其中有重複計算，比如2和3同時是6的因數，6被計算了兩次

這時候就需要容斥原理了，這裡的容斥很巧妙

用vis[i]代表m的第i個因數是否應該做貢獻

用num[i]代表m的第i個因數做了幾次貢獻（被重複計算幾次）

那麼m的第i個因數真正所應該做的貢獻為：

[m/g] * ([m/g]+1)/2 * g * (vis[i]-num[i])

想不明白就畫個Vn圖了解一下

代碼：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int Tmax=;
long long n,m,A[Tmax],in[Tmax],top,g,ans;
int vis[Tmax],num[Tmax];
long long int gcd(long long a,long long b)
{
    return b==?a:gcd(b,a%b);
}
void init()
{
    int i;
    top=;
    for(i=;i<=sqrt(m);i++)
      if(m%i==)
      {
          top++;
          in[top]=i;
          if(i*i!=m)
          {
              top++;
              in[top]=m/i;
          }
      }
    sort(in+,in+top+);
    return;
}
void work()
{
    int i,j;
    for(i=;i<=n;i++)
    {
        if(A[i]>m) g=gcd(A[i],m);
        else g=gcd(m,A[i]);
        for(j=;j<=top;j++)
          if(in[j]%g==) vis[j]=;
    }
    for(i=;i<=top;i++)
    {
        ans+=(m/in[i])*(m/in[i]-)/*in[i]*(vis[i]-num[i]);
        for(j=i+;j<=top;j++)
          if(in[j]%in[i]==) num[j]+=vis[i]-num[i];
    }
    return;
}
int main()
{
    int T,kase,i;
    scanf("%d",&T);
    for(kase=;kase<=T;kase++)
    {
        scanf("%lld%lld",&n,&m);
        for(i=;i<=n;i++)
          scanf("%lld",&A[i]);
        init();
        ans=;
        memset(vis,,sizeof(vis));
        memset(num,,sizeof(num));
        work();
        printf("Case #%d: %lld\n",kase,ans);
    }
    return ;
}