nyoj-Color the necklace（Ploya定理 + 欧拉函数 + 扩展欧几里得（求逆元））

nyoj-Color the necklace（Ploya定理 + 欧拉函数 + 扩展欧几里得（求逆元））

Color the necklace 时间限制：2000 ms | 内存限制：65535 KB 难度：0 描述 As we all know, girls love necklaces, especially nice necklaces. Recently, huicpc229 has fallen in love with a girl; he wants to bring her a necklace as a gift. Now he has n colors, and the necklace is circular and it has n beads, huicpc229 can use his colors to color the necklace. he wants to know how many different kinds of necklaces he can make，he may not use all the n colors. In this problem, the necklace is same when you rotate it around the center of the necklace or turn it over. 输入 First line is the testcase T. Following T lines, each line is an integer n ( 1≤n ≤ 10^9 ) 输出 Output the answer mod 20090531 样例输入 4 1 2 3 4 样例输出 1 3 10 55 来源 3rd Central South China Programming ContestColor the necklace

代码：

#include#include#include#includeusing namespace std;typedef long long LL;const LL mod = 20090531;LL x,y;LL euler(LL p)//欧拉定理{ LL res = p; for(LL i = 2;i <= sqrt(p);i++) { if(p%i==0) { while(p%i==0) p/=i; res = res/i*(i-1); } } if(p > 1) res = res / p * (p-1); return res%mod;}LL fast_pow(LL a,LL b)//快速幂{ LL res = 1; while(b) { if(b&1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res;}void edgcd(LL a,LL b)//求逆元{ if(b == 0) {x = 1;y = 0;return;} edgcd(b,a%b); LL temp = x; x = y;y = temp - a/b*y;}void solve(LL m){ LL res = 0; for(LL i = 1;i <= sqrt(m);i++) { if(m%i==0) { if(m/i != i) res = (res + euler(i)*fast_pow(m,m/i-1))%mod; res = (res + euler(m/i)*fast_pow(m,i-1))%mod; } } if(m&1) { res = (fast_pow(m,(m+1)/2) + res) % mod; edgcd(2,mod); } else { res = (fast_pow(m,m/2+1) + fast_pow(m,m/2) + 2 * res) % mod; edgcd(4,mod); } while(x < 0) x = (x + mod) % mod; printf("%lld\n",x * res % mod);}int main(){ int n; LL m; scanf("%d",&n); while(n--) { scanf("%lld",&m); solve(m); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。