注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

POJ 2154 Color  

2012-03-14 20:27:09|  分类: 组合数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       楼教主出的题目,经典的Polya计数问题,要求统计考虑旋转后用n种颜色对n个珠子的项链染色的方案数,n<=10^9。

       对于n比较小的情况我们可以直接暴力枚举置换群并统计其对应的C(f),考虑旋转i个珠子的循环群,我们可以证明其对应的不动的染色方案C(fi)=n^gcd(i,n)。为什么呢?我们可以这样考虑,假设珠子编号为0~n-1,对于旋转i个珠子的循环群,由于相邻间的珠子对应的旋转后位置还是相邻,所以这个循环群的环必然是大小相等的。假设其环的大小为T,那么就有(T*i)%n=0。假设T*i=k*n,i=g*x,n=g*y,其中g=gcd(i,n)。那么T=k*y/x,因为k为整数,x、y互质,所以使得T最小且为正整数的k=x,那么T=y,整个循环群中环的个数=n/T=g。所以我们可以得到C(fi)=n^gcd(i,n)。那么这个题目就转化为求sum{n^gcd(i,n)},1<=i<=n。

       但是n<=10^9,这个数据范围太大,直接枚举必然超时,我们要考虑优化。观察上面的公式,我们发现虽然i的范围很大,但是gcd(i,n)的值却不多,最多为n的因子的个数。如果我们可以很快求出gcd(i,n)=g时i的个数,那么我们就能够得到一个很高效的算法。假设i=g*x,n=g*y,gcd(i,n)=g的条件为x、y互质,又因为1<=x<=y。所以满足条件的x的个数就是[1,y]里和y互质的数的个数,这就等于phi(y)。欧拉函数的值可以在O(n^(1/2))的复杂度内算出来,于是我们就得到了一个高效的算法。

       实现的时候简单一点的话可以直接枚举找因子,只用枚举到n^1/2,也可以先质因数分解n,然后DFS统计,这样代码复杂一些,但效率要高上不少。
       

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 40000
using namespace std;
bool isprime[ N ];
int prime[ N ],pcnt;
int factor[ 50 ],fcnt[ 50 ],fv[50],fp,ans;
int nmod[50];
void initprime( void ){
memset( isprime,true,sizeof( isprime ) );
for( int i=2;i<N;i++ ){
if( isprime[ i ] ) prime[ pcnt++ ]=i;
for( int j=0;j<pcnt&&i*prime[ j ]<N;j++ ){
isprime[ i*prime[ j ] ]=false;
if( i%prime[ j ]==0 ) break;
}
}
}
void fac( int n ){
fp=0;
for( int i=0;i<pcnt&&n>1;i++ )
if( n%prime[ i ]==0 ){
factor[fp++]=prime[i],fv[fp-1]=1;
for( fcnt[fp-1]=0;n%prime[ i ]==0;n/=prime[ i ],fcnt[ fp-1 ]++,fv[fp-1]*=prime[i] );
}
if( n>1 ) factor[fp]=n,fcnt[fp]=1,fv[fp++]=n;
}
void DFS( int mod,int g,int phi,int d ){
if( d==fp ){
phi%=mod,g--;
int res=1;
for( int i=0;g;g>>=1,i++ )
if( g&1 )
res=( res*nmod[i] )%mod;
ans=( ans+phi*res )%mod;
return;
}
for( int i=0,p=fv[d];i<=fcnt[ d ];i++,p/=factor[d] ) DFS( mod,g*(fv[d]/p),phi*(p-p/factor[d]),d+1 );
}
int main( void ){
// freopen( "in.in","r",stdin );
initprime();
int cas,n,mod;
cin>>cas;
while( cas-- ){
cin>>n>>mod;
if( n==1 ){
cout<<1%mod<<endl;
continue;
}
fac( n );
ans=0;
nmod[0]=n%mod;
for( int i=1;i<=30;i++ ) nmod[i]=(nmod[i-1]*nmod[i-1])%mod;
DFS( mod,1,1,0 );
cout<<ans<<endl;
}
}

































































































































  评论这张
 
阅读(739)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017