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
西風蕭瑟 閱讀(2438)
評論(1) 編輯 收藏 引用 所屬分類:
動態規劃