HDU 5868 Different Circle Permutation（burnside 引理）

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5868

Description

Input

Output

Sample Input

Sample Output

题意：

题解：

代码：

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9+7 ;

struct matrix {

    long long x1,x2 ;

    long long x3,x4 ;

};

matrix mul(matrix a,matrix b){

    matrix ans ;

    ans.x1 = (a.x1*b.x1 + a.x2*b.x3)%mod ;

    ans.x2 = (a.x1*b.x2 + a.x2*b.x4)%mod ;

    ans.x3 = (a.x3*b.x1 + a.x4*b.x3)%mod ;

    ans.x4 = (a.x3*b.x2 + a.x4*b.x4)%mod ;

    return ans ;

}

long long quick_matrix(long long x){

    x -= 4 ;

    matrix ans,cal ;

    ans.x1 = ans.x2 = ans.x3 = 1 ; ans.x4 = 0 ;

    cal.x1 = cal.x2 = cal.x3 = 1 ; cal.x4 = 0 ;

    while (x){

        if (x%2)

            ans = mul(ans,cal) ;

        cal = mul(cal,cal) ;

        x >>= 1 ;

    }

    return (ans.x1*4+ans.x2*3)%mod ;

}

long long fx(long long x){

    if (x == 1)

        return 1;

    else if (x == 2)

        return 3;

    else if (x == 3)

        return 4;

    else return quick_matrix(x) ;

}

long long quick(long long a,long long n){

    long long ans = 1 ;

    long long cal = a ;

    while (n){

        if (n%2)

            ans = (ans*cal)%mod ;

        cal = (cal*cal)%mod;

        n >>= 1;

    }

    return ans ;

}

long long euler(long long n)

{

    long long ans = n;

    long long i;

    for (i = 2; i*i <= n; i++){

        if (n%i == 0){

            while (n%i == 0)

                n /= i;

            ans = ans/i*(i-1) ;

        }

    }

    if (n != 1)

        ans = ans/n*(n-1);

    return ans;

}

long long solve(long long n){

    if (n == 1)

        return 2;

    long long ans = 0;

    long long nn = n ;

    long long d;

    long long i;

    for (i = 1; i*i < n; i++){

        if (n%i == 0){

            ans = (ans + fx(i)*euler(nn/i) + fx(nn/i)*euler(i))%mod ;

        }

    }

    if (i*i == n)

        ans = (ans + fx(i)*euler(i))%mod ;

    return (ans*quick(nn,mod-2))%mod;

}

int main()

{

    long long n;

    while (~scanf("%lld",&n))

        printf("%lld\n",solve(n)) ;

    return 0 ;

}