Poj 2154 Color (Polya计数欧拉函数优化)

深碍√TFBOYSˉ_ 2022-09-17 14:15 125阅读 0赞

题意：给出两个整数n和p，代表一串项链有n个珠子，用n种颜色对其染色，有些颜色可以不用，求不同的项链数，结果模p。

参考了：http://blog.csdn.net/wsniyufang/article/details/6671122

思路：置换只有旋转一种方式，那么共有n个置换。

顺时针旋转i格的置换中，循环节的个数为gcd（i，n），每个循环节的长度L为n/gcd(i,n)

普通求法: 枚举i，则 ∑n^( gcd(n,i) ) 0<=i<n 复杂度过高

优化:枚举环的长度L ，由于L|N (N可被L整除)，n/L | n ，所以L可以从1取到sqrt(n)

枚举了L，再计算有多少个i使得0<=i<=n-1并且gcd（i,n）＝n/L。

不妨令 a=n/L = gcd(n , i) , 再令i = at

那么当且仅当gcd(L,t)=1时候，才有 Gcd(i,n)=gcd(a\*L,a\*t)=a。

因为0<=i<n,所以0<=t<n/a=L

所以满足这个条件的t的个数为Euler(L)，即phi(L)

也就是说当循环节长度为L，个数为N/L时，有phi(L) 种置换。

最后还要注意：polya 定理最后要除以|G| ，由于有取模操作，就要用到逆元，但是题目并没有说p和n互素，所以可能不存在逆元。

解决方法：颜色和珠子个数是相等的，也就是置换的总数与N相等，所以在快速幂的时候-1就行了

那么最后统计一下就是 ∑(phi(L) \* N^(N/L-1) ) % p (L即枚举值)

本题时间卡的很紧，尽量使用int，快速幂的写法貌似也很讲究……我的代码跑了1532ms

求欧拉函数时预处理素数貌似也能节省不少时间，详见：http://zhulinb123.blog.163.com/blog/static/184414043201182351033633/

#include <cstdio>
    
    int euler (int n)
    {
        int i,ans=n;
        for (i=2;i*i<=n;i++) if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
        if(n>1) ans=ans/n*(n-1);
        return ans;
    }
    
    __int64 modPow (__int64 s,__int64 index,__int64 mod)  
    //返回值(s^index)%mod    
    {      
        __int64 ans=1;      
        s%=mod;   //先对底数取模比较好
        while (index>=1)      
        {      
            if ((index&1)==1)   //奇数      
                ans=(ans*s)%mod;      
            index>>=1;      
            s=s*s%mod;      
        }      
        return ans;
    }
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,i;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		int n,mod;
    		scanf("%d%d",&n,&mod);
    		int ans=0;
    		for (i=1;i*i<n;i++)  //枚举L
    			if (n%i==0)
    			{
    				ans=(ans+euler(n/i)*modPow(n,i-1,mod)%mod)%mod;
    				ans=(ans+euler(i)*modPow(n,n/i-1,mod)%mod)%mod;
                }   
            if (i*i==n)
                ans=(ans+euler(i)*modPow(n,i-1,mod)%mod)%mod;  
            printf("%d\n",ans%mod);
    	}
    	return 0;
    }