UPC:2526 Color the necklace

2019-04-14 21:17发布

站内文章 / 模拟电子
17068 0 1392
http://acm.upc.edu.cn/problem.php?id=2526   这个题是http://blog.csdn.net/kkkwjx/article/details/21525325的加强版，也是Polya定理非常经典的题目。 由于最后要除以2和4，在模运算里面直接除是不行的，要乘上2或4模MOD的乘法逆元。 用到了Polya定理，求欧拉函数，求逆元，快速幂模 #include #include #include #include #define ll long long #define MOD 20090531 using namespace std; void gcd(ll a,ll b,ll &d,ll &x,ll &y) { if(!b) { d=a; x=1; y=0; } else { gcd(b,a%b,d,y,x); y-=x*(a/b); } } ll inv(ll a,ll n) { ll d,x,y; gcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } ll pow_mod(ll a,ll b) { ll res=1; while(b) { if(b&1)res=res*a%MOD; b=b>>1; a=a*a%MOD; } return res; } int euler_phi(int n) { int m=sqrt(n+0.5); int ans=n; for(int i=2; i<=m; ++i) if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) n=n/i; } if(n>1) ans=ans/n*(n-1); return ans; } ll mod(ll val) { return (val%MOD+MOD)%MOD; } int main() { int T; scanf("%d",&T); ll n2=inv(2,MOD),n4=inv(4,MOD); while(T--) { int n; scanf("%d",&n); int s=sqrt(n+0.5); ll ans=0; for(int i=1; i<=s; ++i) if(n%i==0) { if(n/i!=i) { ans+=mod(euler_phi(n/i)*pow_mod(n,i-1)); ans+=mod(euler_phi(i)*pow_mod(n,n/i-1)); ans=mod(ans); } else ans+=mod(euler_phi(i)*pow_mod(n,n/i-1)); } ans=mod(ans*n2); ll res=0; if(n%2) { res=mod(pow_mod(n,(n+1)/2)); res=mod(res*n2); } else { res=mod(mod(pow_mod(n,n/2))+mod(pow_mod(n,n/2+1))); res=mod(res*n4); } printf("%lld ",mod(ans+res)); } return 0; }
     

热门文章