Invoker
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 122768/62768 K (Java/Others)
Total Submission(s): 515 Accepted 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 )
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: 1HintFor 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
这个题是一个很裸露的波利亚定理的运用
但是最后取余要用逆元。
但是这个题比较巧妙，因为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;
}