這個(gè)題一看就知道是求歐拉函數(shù)。歐拉函數(shù)描述的正式題意。歐拉函數(shù)的理解可以按照算法導(dǎo)論上面的說(shuō)法，對(duì)0-N-1進(jìn)行篩選素?cái)?shù)。
那么公式n
∏(1-1/p)，其中p是n的素?cái)?shù)因子，就可以得到直觀的理解了。但是計(jì)算的時(shí)候，會(huì)將這個(gè)式子變形下，得到另外一個(gè)形式。
如圖所示：
.jpg)
但是這個(gè)題，需要考慮下，有可能n是個(gè)大素?cái)?shù)，直接進(jìn)行因子分解的話會(huì)超時(shí)的。怎么辦了，只能在分解的時(shí)候判斷n是不是已經(jīng)成為
素?cái)?shù)了，如果是素?cái)?shù)，答案再乘以n-1就行了。為了加快判斷，我用5mb的空間搞了個(gè)素?cái)?shù)表，大于5000000的數(shù)字只能循環(huán)判斷了。
代碼如下，注意求歐拉函數(shù)的代碼部分：
#include <stdio.h>
#include <math.h>
#define MAX (5000000)
bool bPrime[MAX];//false表示素?cái)?shù)
void InitPrime()
{
bPrime[0] = bPrime[1] = true;
int nMax = sqrt((double)MAX) + 1;
for (int i = 2; i <= nMax; ++i)
{
if (!bPrime[i])
for (int j = i * 2; j < MAX; j += i)
{
bPrime[j] = true;
}
}
}
bool IsPrime(int nN)
{
if (nN < MAX)
{
return !bPrime[nN];
}
else
{
int nMax = sqrt((double)nN) + 1;
for (int i = 2; i <= nMax; ++i)
{
if (nN % i == 0)
{
return false;
}
}
return true;
}
}
int main()
{
int nN;
InitPrime();
while (scanf("%d", &nN), nN)
{
if (nN == 1){printf("0\n");continue;}
int nAns = 1;
for (int i = 2; i <= nN; ++i)
{
if (IsPrime(nN))
{
nAns *= nN - 1;
break;
}
if (nN % i == 0)
{
nAns *= i - 1;
nN /= i;
while (nN % i == 0)
{
nAns *= i;
nN /= i;
}
}
}
printf("%d\n", nAns);
}
return 0;
}