HDU 3923 Invoker(polya定理+乘法逆元（扩展欧几里德+费马小定理）)

Invoker

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 122768/62768K (Java/Other)

Total Submission(s) : 1 Accepted Submission(s) : 0

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

乘法逆元：http://blog.csdn.net/yukizzz/article/details/51105009

乘法逆元什么用：

　　若对于数字A,C 存在X，使A * X = 1 (mod C) ,那么称X为 A 对C的乘法逆元。

　　逆元的作用？让我们来看下面的例子:
　　12 / 4 mod 7 = ? 很显然结果是3
　　我们现在对于数对 (4,7), 可以知道 X = 2是 4 对7的乘法逆元即2*4=1（mod 7)
　　那么我们有(12 / 4) * (4 * 2 ) = (?) * (1) (mod 7)
　　除法被完美地转化为了乘法。

1. 用了费马小定理+快速幂求乘法逆元

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
int T;
const long long mod=1000000007;
long long res,n,m;
long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}
long long poww(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if (b%2==1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%lld%lld",&m,&n);
        res=0;
        for(long long i=0;i<n;i++)
          res=(res+poww(m,gcd(n,i)))%mod;
        if(n%2==1)
          res=(res+poww(m,(n+1)/2)*n)%mod;
        else
        {
           res=(res+poww(m,n/2+1)*(n/2))%mod;
           res=(res+poww(m,n/2)*(n/2))%mod;
        }
        printf("Case #%d: ",t);
        printf("%lld
",(res*poww(2*n,mod-2))%mod);
    }
    return 0;
}

2.用扩展欧几里德求逆元

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
int T;
const long long mod=1000000007;
long long res;
int m,n;

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
long long poww(long long a,int b)
{
    long long ans=1;
    while(b)
    {
        if (b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return ans;
}

//返回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==0&&b==0) return -1;//无最大公约数
    if(b==0){x=1;y=0;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==1) return (x%n+n)%n;
    else return -1;
}

int main()
{
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%d%d",&m,&n);
        res=0;
        for(int i=0;i<n;i++)
          res=(res+poww(m,gcd(n,i)))%mod;
        if(n%2==1)
          res=(res+poww(m,(n+1)/2)*n)%mod;
        else
        {
           res=(res+poww(m,n/2+1)*(n/2))%mod;
           res=(res+poww(m,n/2)*(n/2))%mod;
        }
        printf("Case #%d: ",t);
        printf("%I64d
",(res*mod_reverse(2*n,mod))%mod);
    }
    return 0;
}