http://acm.hdu.edu.cn/showproblem.php?pid=2824
定義： 對(duì)于正整數(shù)n，φ(n)是小于或等于n的正整數(shù)中，與n互質(zhì)的數(shù)的數(shù)目；
例如: φ(8) = 4, 因?yàn)?，3，5，7均和8互質(zhì)。
性質(zhì)： 1. 若p是質(zhì)數(shù)，φ（p）= p-1.
2. 若n是質(zhì)數(shù)p的k次冪，φ（n）= （p-1）p^(k-1)
因?yàn)槌藀的倍數(shù)都與n互質(zhì)
3. 歐拉函數(shù)是積性函數(shù)，若m，n互質(zhì)，φ（mn）= φ(m)φ(n)
根據(jù)這3條性質(zhì)我們就可以退出一個(gè)整數(shù)的歐拉函數(shù)的公式，因?yàn)橐粋€(gè)數(shù)總可以一些質(zhì)數(shù)的乘積的形式。
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)
在程序中利用歐拉函數(shù)如下性質(zhì)，可以快速求出歐拉函數(shù)的值(a為N的質(zhì)因素)
若(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種求歐拉函數(shù)的算法
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 }
利用素?cái)?shù)篩選：
void init()
{
__int64 i, j;
p[0] = 1; //記錄素?cái)?shù)個(gè)數(shù)
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;
} //篩素?cái)?shù)
e[1] = 1;
for (i=1; i<=p[0]; i++)
e[p[i]] = p[i] - 1; //初始化素?cái)?shù)的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;
} // 利用上述性質(zhì)求解
}
}
return ;
}
明顯第一種的編程復(fù)雜度要低很多
所以，一般情況下（N不是很大），采用第一種即可；
貼在這里供以后復(fù)習(xí)
posted on 2009-12-01 19:21
西風(fēng)蕭瑟 閱讀(2438)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
動(dòng)態(tài)規(guī)劃