Invoker
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 122768/62768 K (Java/Others)
Total Submission(s): 907 Accepted Submission(s): 364
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.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )
3 4
1 2
Case #2: 1
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 /
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
const int MOD= 1e9+; long long pow_m(long long a,int n)
{
long long ret = ;
long long temp = a%MOD;
while(n)
{
if(n&)
{
ret *= temp;
ret %= MOD;
}
temp *= temp;
temp %= MOD;
n >>= ;
}
return ret;
}
int gcd(int a,int b)
{
if(b == )return a;
return gcd(b,a%b);
}
//******************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
if(a==&&b==) return -;//无最大公约数
if(b==){x=;y=;return a;}
long long d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
long long mod_reverse(long long a,long long n)
{
long long x,y;
long long d=extend_gcd(a,n,x,y);
if(d==) return (x%n+n)%n;
else return -;
} int main()
{
int T;
int m,n;
scanf("%d",&T);
int iCase = ;
while(T--)
{
iCase++;
scanf("%d%d",&m,&n);
long long ans = ;
if(n%==)
{
ans = n/*pow_m(m,n/)+n/*pow_m(m,n/+);
ans %= MOD;
}
else ans = n*pow_m(m,n/+);
//cout<<ans<<endl;
for(int i = ;i < n;i++)
{
ans += pow_m(m,gcd(i,n));
ans %= MOD;
//cout<<ans<<endl;
}
ans *= mod_reverse(*n,MOD);
ans%=MOD;
printf("Case #%d: %I64d\n",iCase,ans);
}
return ;
}