2154__ac.cpp

各种算法

#include <iostream>
#include <memory>
#include <cstdlib>
#define M   35005
#define mr 35000
using namespace std;
/*X (X <= 3500),N and P (1 <= N <= 1000000000, 1 <= P <= 30000)*/
int n, p, l=1, pn=0, test;
int prim[10001], notp[M];/*n/logn<15000*/
//prim[]存储素数，notp[]用来标记素数，pn用来计数。 
int prime()
{//线性筛选素数
	int i, j;
	memset(notp, 0, sizeof(notp));
	for(i = 2; i < mr; i++)
	{
		if(notp[i] == 0)	prim[pn++] = i;
		for(j = 0; prim[j]*i < mr&& j < pn; j++)
		{
			notp[ i*prim[j] ] = 1;
			if(i % prim[j] == 0)	break;//线性的关键体现
		}
	}
      return 0;
}
int phi(int n)
{//线性欧拉函数，Caclulate,Euler(n)%p.
//Pi为n的质数因子
//n = IIpow(Pi,Ai)
//欧拉公式Euler(n) = II(Pi-1)pow(Pi,Ai-1) = n*II(1-1/Pi) 
	int tem = n, i;
	for(i = 0; i < pn && prim[i]*prim[i] <= tem; i++){
		if(tem % prim[i] == 0)
		{
			n = n - (n/prim[i]);
			do	tem /= prim[i];
			while(tem % prim[i] == 0);
		}
	}
	if(tem != 1) n -= n/tem;
	return n%p;
}
int exp_mod(int m)
{//Calculate n.^m%p.
	int tem, s, ans;
	tem = m;
	ans = 1;
	s = n % p;
	while(tem > 0)
	{
		if(tem % 2 == 1) ans = (ans * s) % p;
		tem /= 2;
		s = (s * s) % p;
	}
	return ans;
}
int main()
{
	prime();//求3500内的质数
	scanf("%d",&test);
	while(test--)
	{
		int i, ans=0;
		scanf("%d%d",&n, &p);
		for(l = 1; l*l <= n; l++)
		if(l*l == n)//枚举循环长度l，找出相应的i的个数：gcd(i,n)=n/l.
			ans = (ans + phi(l) * exp_mod(l-1)) % p;
		else
		if(n%l == 0)//有长度为l的循环，就会有长度为n/l的循环节。 
			ans = (ans + phi(l) * exp_mod(n/l-1) + phi(n/l) * exp_mod(l-1)) %p;
		printf("%d\n",ans);
	}
	return 0;
}
/*	http://hi.baidu.com/yufuwan1/blog/item/59907a8220427796f603a6b6.html
题目要求：给出两个整数n和p，代表n个珠子，n种颜色，要求不同的项链数，并对结果mod（p）处理。
所属类型：组合题
应用知识：polya，Euler
分析：这题和1286，2409 都有点类似，不同之处在于，只考虑旋转，不考虑翻转；
因此相对前面两个题目应该说是更简单，但一看数据范围，就不是这么回事了，
1286和2409完全可以直接循环处理，但这题目n最大达100000000，显然会TLE，
故需寻求更佳的解决方案。
可以用欧拉函数进行优化，或者用Mobius反演定理进行优化。下面讲解一下用欧拉优化的方法：
旋转：顺时针旋转i格的置换中，循环的个数为gcd（i，n），每个循环的长度为n/gcd(i,n)。
如果枚举旋转的格数i，复杂度显然较高。有没有好方法呢？可以不枚举i，反过来枚举L。
由于L|N,枚举了L，再计算有多少个i使得0<=i<=n-1并且L＝gcd(i, n)。即gcd（i,n）＝n/L。
不妨设a＝n/L=gcd(i, n),
不妨设i＝a*t则当且仅当gcd(t,L)=1时
Gcd(i,n)=gcd(a*t,a*L)=a。
因为0<=i<n,所以0<=t<n/a=L.
所以满足这个条件的t的个数为Euler(L).
现在结果已经很明显了。Ans＝∑(Euler(L)*(n.^(L-1)))%p。(L为符合上面假设条件的所有数）.
复杂度分析：线性筛选素数，线性筛选欧拉函数因子，枚举L，这些都是在线性的复杂度内完成的。
*/

/*
欧拉函数的知识见百度百科

至于循环节为什么为g(n,i) ,如求1-12的环,转角度数为　i*360/12,i为转角基数　＝　５时
1 -- 12 1 -- 12 1 -- 12 1-- 12 1 -- 12 1
当绕五圈后走到1处，中间无重复（？）。n = 12
则 12 / 5 = 2...2	n / i = k...t    即求n与i的最小公倍数 m，所走的点数为m/i)，
则循环节数为n/(m/i) 即求最大公约数gcd(n,i);
*/