首页 > 代码库 > POJ 2154 Color(组合数学-波利亚计数,数论-欧拉函数,数论-整数快速幂)
POJ 2154 Color(组合数学-波利亚计数,数论-欧拉函数,数论-整数快速幂)
Color
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 7693 | Accepted: 2522 |
Description
Beads of N colors are connected together into a circular necklace of N beads (N<=1000000000). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the N colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected.
You only need to output the answer module a given number P.
You only need to output the answer module a given number P.
Input
The first line of the input is an integer X (X <= 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 <= N <= 1000000000, 1 <= P <= 30000), representing a test case.
Output
For each test case, output one line containing the answer.
Sample Input
5 1 30000 2 30000 3 30000 4 30000 5 30000
Sample Output
1 3 11 70 629
Source
POJ Monthly,Lou Tiancheng
题目大意:
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。