[ACM] hdu 3923 Invoker (Poyla計數，快速冪運算，擴展歐幾裡得或費馬小定理）

 

Invoker

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

HintFor 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

 

 

 

解題思路：

Polya計數。題目可轉化為用c種顏色給n個珠子的項鏈染色，問一共有多少種顏色方案。本題要對結果取模1000000007

 

1.旋轉。

將環順時針旋轉i格後，循環節個數為gcd(n,i)， 染色方案為 ∑c^gcd(n,i) 其中 i=1,2,3,4,....n

2.翻轉。

這裡也得考慮兩種情況。

當n為奇數時，共有n個循環節個數為（n/2+1)的循環群，還有的資料上說是環的個數為（n/2+1) ，注意這是計算機上的表示，n/2整型相除計算機得到的是整數，其實應該寫成（n+1)/2。，染色方案為 n*c^(n/2+1)

為什麼n個循環節個數為（n/2+1)的循環群呢？我的理解是這樣的，或許不太對。。。

拿正三角形為例，給它三個頂點染色， 對稱軸是一個頂點與其對邊終點連線所在的直線，這樣的直線有3（n=3，即n個頂點) 條，共有3（n)個循環群。假設第一個頂點在對稱軸上，那麼第二個頂點經過對稱軸翻轉肯定和第三個頂點重合，那麼 （2,3）是一個循環節，（1）自己是一個循環節，循環節個數為2，即（n+1/2)。

當n為偶數時，共有n個循環群，其中有n/2個的循環節個數為（n/2 +1)， 有n/2個的循環節個數為（n/2)。

拿正方形為例，四個頂點從左上角順時針編號1,2,3,4.

當以1,3頂點連線所在直線為對稱軸時（對角的兩個頂點）,這樣對稱軸有2個（n/2)，經過翻轉，2,4 重合，1和1重合，3和3重合，那麼循環節的個數為3（2,4） （1）（3）, 即(n/2+1)。 染色方案為 (n/2)*c^(n/2+1)

當以兩條相對平行的邊的中點連線所在直線為對稱軸時，比如以線段1,2的中點和3,4的中點連線的所在直線為對稱軸，這樣的對稱軸有兩個（n/2)，經過翻轉，1,2重合，3,4重合，循環節的個數為2，（1,2）（3,4），即（n/2)。，也就是誰和誰重合，誰就和誰在一個循環節裡。染色方案為(n/2)*c^(n/2)

 

最後累加方案得到ans， 再除以置換群的個數2*n，即 ans/(2*n)%mod即為最後答案。但這裡要特別注意，ans是在計算過程中不斷取模得到的數，ans,2*n都在模剩余系中，不能直接參與除法計算，因為有公式a*b%mod=(a%mod*b%mod)%mod，除法對取余不滿足結合律，a/b!=((a%mod)/(b%mod))%mod ，在計算 ans/(2*n）%mod時，可以轉化為 ans*inv(2*n)%mod ,其中 inv(2*n)是2*n關於mod的逆元，保證乘以inv(2*n)和除以 2*n 對於最後的答案取余mod是一樣。

所以現在的問題是怎樣求一個數關於模P的逆元。

 

方法1：擴展歐幾裡得。 ax=1(mod P), gcd(a,p)=1， 其中x為a的逆元，就是我們所求，ax=PY+1, ax-Py=1, 所以用擴展歐幾裡得可以求出x。

方法2：費馬小定理： 如果模P是素數的話，那麼inv(a)=pow(a,p-2)%p; 等式右邊用快速冪運算可以得出。

參考：http://www.xuebuyuan.com/1394391.html

 

代碼：

 

#include 
using namespace std;
typedef long long LL;
const LL mod=1000000007;
LL c,n;

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

LL power(LL p,LL n)//快速冪運算
{
    LL ans=1;
    while(n)
    {
        if(n&1)
            ans=ans*p%mod;
        p=p*p%mod;
        n/=2;
    }
    return ans;
}
LL  exgcd(LL a,LL b,LL &x,LL &y)//擴展歐幾裡得算法，返回a,b的最大公約數,ax+by=gcd(a,b)，x,y為方程的一組解
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    long long d=exgcd(b,a%b,x,y);
    long long t=x;
    x=y;
    y=t-a/b*y;
    return d;
}

int main()
{
    int t;cin>>t;
    int cas=1;
    while(t--)
    {
        cin>>c>>n;
        int ans=0;
        for(LL i=1;i<=n;i++)
        {
            ans+=power(c,gcd(n,i));
            ans%=mod;
        }
        if(n&1)
            ans+=(n*power(c,n/2+1))%mod;
        else
            ans+=((n/2*power(c,n/2+1))%mod+(n/2*power(c,n/2))%mod)%mod; //注意mod的位置
        ans%=mod;
        LL x,y;
        exgcd(2*n,mod,x,y);
        //x=power(2*n,mod-2)%mod;//第二種方法
        x=(x+mod)%mod;
        cout<<"Case #"<