HDU/HDOJ 3923 2011 BJTU多校联合 波利亚原理

Invoker

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 122768/62768 K (Java/Others)
Total Submission(s): 515Accepted Submission(s): 163

Problem Description

On of Vance's favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.

In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

Input

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )

Output

For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.

Sample Input

2
3 4
1 2

Sample Output

Case #1: 21
Case #2: 1


Hint
For Case #1: we assume a,b,c are the 3 kinds of elements.
Here are the 21 different arrangements to invoke the skills
/ aaaa / aaab / aaac / aabb / aabc / aacc / abab / 
/ abac / abbb / abbc / abcb / abcc / acac / acbc /
/ accc / bbbb / bbbc / bbcc / bcbc / bccc / cccc /
 

Source

2011 Multi-University Training Contest 9 - Host by BJTU

这个题是一个很裸露的波利亚定理的运用

但是最后取余要用逆元。

但是这个题比较巧妙，因为mod=1000000007，他是一个质数，于是要求某一个数的逆元的话直接mod-2次方，然后二分幂去模就行了

至于波利亚定理，我同样使用的POJ 2154以及POJ 2409的写法

我的代码：

#include<stdio.h>
#include<string.h>

typedef __int64 ll;
const ll mod=1000000007;

ll eular(ll n)
{
	ll ret=1,i;
	for(i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			ret=ret*(i-1);
			n=n/i;
			while(n%i==0)
			{
				n=n/i;
				ret=ret*i;
			}
		}
		if(n==1)
			break;
	}
	if(n>1)
		ret=ret*(n-1);
	return ret%mod;
}

ll exmod(ll p,ll n)
{
	ll sq=1;
	while(n>0)
	{
		if(n%2==1)
			sq=(sq%mod)*(p%mod)%mod;
		p=(p%mod)*(p%mod)%mod;
		n=n/2;
	}
	return sq%mod;
}

int main()
{
	ll n,ans,i,m,t,T;
	scanf("%I64d",&T);
	for(t=1;t<=T;t++)
	{
		scanf("%I64d%I64d",&m,&n);
		ans=0;
		for(i=1;i*i<n;i++)
		{
			if(n%i==0)
			{
				ans=(ans+eular(n/i)*exmod(m,i))%mod;
				ans=(ans+eular(i)*exmod(m,n/i))%mod;
			}
		}
		if(i*i==n)
			ans=(ans+eular(n/i)*exmod(m,i))%mod;
		if(n&1)
			ans=(ans+exmod(m,n/2+1)*n)%mod;
		else
			ans=(ans+exmod(m,n/2)*n/2+exmod(m,n/2+1)*n/2)%mod;
		ll re=exmod(2*n,mod-2);
		printf("Case #%I64d: %I64d\n",t,(ans%mod)*(re%mod)%mod);
	}
	return 0;
}