POJ 2154 Color（组合数学-波利亚计数,数论-欧拉函数,数论-整数快速幂）

Description

Input

Output

Sample Input

5
1 30000
2 30000
3 30000
4 30000
5 30000

Sample Output

1
3
11
70
629

Source

题目大意：

T组测试数据，每组一个n表示1个项链有n个颜色可以涂在n个钻石上，通过旋转相同的算一种方案，问你方案数是多少？

解题思路：

很裸的波利亚计数，转化为的公式就是 ans=sum{ n^( gcd(1,n)-1  ) ,n^( gcd(2,n)-1  ),n^( gcd(3,n)-1  ) .....n^( gcd(n,n)-1  )     }，因为这个n比较大10^9，所以暴力超时。

因此枚举 gcd(k,n)=l 的有多少个，也就是 k=l*x ，n=l*y，也就是gcd(x,y)=1,也就是找到 1~y与y互质的数有多少个，答案：欧拉函数

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
int n,p;

inline ll getPhi(int x){
    ll ans=x;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}

inline ll pow_mod(ll a,ll b){
    ll sum=1;
    while(b>0){
        if(b&1) sum=(sum*a)%p;
        a=(a*a)%p;
        b/=2;
    }
    return sum%p;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t-- >0){
        scanf("%d%d",&n,&p);
        ll ans=0;
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                if(i*i==n) ans=(ans+(getPhi(i)*pow_mod(n,i-1))%p)%p;
                else{
                    ans=(ans+(getPhi(n/i)*pow_mod(n,i-1))%p)%p;
                    ans=(ans+(getPhi(i)*pow_mod(n,n/i-1))%p)%p;
                }
            }
        }
        printf("%lld\n",ans%p);
    }
    return 0;
}

POJ 2154 Color（组合数学-波利亚计数,数论-欧拉函数,数论-整数快速幂）,布布扣,bubuko.com

POJ 2154 Color（组合数学-波利亚计数,数论-欧拉函数,数论-整数快速幂）

原文：http://blog.csdn.net/a1061747415/article/details/38331969