HDU 5514 Frogs

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5514
标题:m個の石で囲まれ、番号はそれぞれ0からm-1、現在はn匹のカエルがいて、いずれも0番の石の上にいて、i匹目のカエルは現在の番号posの石から(pos+ai)%mの石の上に飛びます.しかし、カエルに通られた石はすべて占領され、このm個の石の中のすべての占領された石の番号とを求めます.
 構想:反発定理、gcd(ai,m)はi番目のカエルが跳ぶことができる石の最小番号(0を除く)であり、(m-1)/gcd(ai,m)はこのカエルが跳ぶことができる石の数である.すべてのgcd(ai,m)はmの因数であるため,まずmを因数に分解し,その後反発して答えを統計する.x=gcd(ai,m)が1つ現れると、すべてのxの倍数の因数が現れたとみなされ、計算時にxの倍数をk回加算するとpkの倍数からk回減算されます.

#include 
#include 
#include 
#include 

using namespace std;

#define rep(i,j,k) for(int i = j;i<=k;i++)
#define Rep(i,j,k) for(int i = j;i>=k;i--
#define Clean(x,y) memset(x,y,sizeof(x))
#define LL long long

int T,n,m;
int fact[1009];
int sum;
int appear[1009];
int cnt[1009];

void init(int x)
{
    Clean(appear,0);
    Clean(cnt,0);
	sum = 0;
	for(int i = 1;i*i<=x; i++)
	{
		if ( x % i == 0 )
		{
			fact[++sum] = i;
			if ( i * i != x ) fact[++sum] = x/i;
		}
	}
}


int gcd(int a , int b)
{
	return (a%b==0)?b:gcd(b,a%b);
}

int main()
{

	cin>>T;
	rep(kase,1,T)
	{
		LL ans = 0;
		scanf("%d %d",&n,&m);
		init(m);
		sort(fact+1,fact+1+sum);
		sum--; //    m
		int a;
		rep(i,1,n)
		{
			scanf("%d",&a);
			int x = gcd(m,a);
            rep(i,1,sum)
                if ( fact[i] % x == 0 ) appear[i] = 1; //  fact[i]          。
		}

        rep(i,1,sum)
            if ( cnt[i] != appear[i] ) //    ，    
            {
                LL t = (m-1)/fact[i];  // fact[i](1+2+3+...+ (m-1)/fact[i] )
                ans += t*(t+1) / 2 * fact[i] * ( appear[i] - cnt[i] ); 
                rep(j,i+1,sum)
                    if ( fact[j] % fact[i] == 0 ) cnt[j] += appear[i] - cnt[i]; //   fact[i]         fact[i]         

  。
            }
        printf("Case #%d: %I64d
",kase,ans);
	}

	return 0;
}