http://acm.hdu.edu.cn/showproblem.php?pid=2824
定义： 对于正整数n，φ(n)是小于或等于n的正整数中，与n互质的数的数目；
例如: φ(8) = 4, 因为1，3，5，7均和8互质。
性质： 1. 若p是质数，φ（p）= p-1.
2. 若n是质数p的k次幂，φ（n）= （p-1）p^(k-1)
因为除了p的倍数都与n互质
3. 欧拉函数是积性函数，若m，n互质，φ（mn）= φ(m)φ(n)
根据这3条性质我们就可以退出一个整数的欧拉函数的公式，因为一个数总可以一些质数的乘积的形式。
E(k) = (p1-1)(p2-1)…(pi-1)*(p1^(a1-1))(p2^(a2-1))…(pi^(ai-1))
= k*(p1-1)(p2-1)…(pi-1)/(p1*p2*…pi)
= k*(1-1/p1)*(1-1/p2)…(1-1/pk)
在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素)
若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
以下是2种求欧拉函数的算法
1 void init()
2 {
3 __int64 i,j;
4 e[1] = 1;
5 for(i=2;i<=N;i++)
6 if(!e[i])
7 {
8 for(j=i; j<=N; j+=i)
9 {
10 if (!e[j])
11 e[j] = j;
12 e[j] = e[j] / i * (i-1);
13 }
14 }
15 }
利用素数筛选：
void init()
{
__int64 i, j;
p[0] = 1; //记录素数个数
p[1] = 2;
for (i=3; i<N; i+=2)
{
if (hash[i])
continue;
p[++p[0]] = i;
for (j=i*i; j<N; j+=i)
hash[j] = true;
} //筛素数
e[1] = 1;
for (i=1; i<=p[0]; i++)
e[p[i]] = p[i] - 1; //初始化素数的phi
for (i=2; i<N; i++)
{
if(!e[i])
{
for (j=1; j<=p[0]; j++)
if (i % p[j]==0)
{
if (i / p[j] % p[j])
e[i] = e[i / p[j]] * e[p[j]];
else
e[i] = e[i / p[j] ]* p[j];
break;
} // 利用上述性质求解
}
}
return ;
}
明显第一种的编程复杂度要低很多
所以，一般情况下（N不是很大），采用第一种即可；
贴在这里供以后复习
posted on 2009-12-01 19:21
西风萧瑟 阅读(2374)
评论(1) 编辑 收藏 引用 所属分类:
动态规划