洛谷题解 UVA10299 【Relatives】

发表于 | 阅读次数：
本文字数： 1.3k | 阅读时长 ≈ 1 分钟

题意简述：

给你一个数$n$，求$\phi(n) $的值。

解题思路：

$\phi(n) $即欧拉函数，其一种形式为:

$\phi(n)=n \prod_{i=1}^{n} (\frac{p_n-1}{p_n})$

其中$p$为$n$的质因数，且每个质因数互异，对于符号 $\prod$理解为$ \prod_{i=1}^{n}= A_1 * A_2 * … * A_n $

那这题就变成了简单的分解质因数了，分解完了套公式即可

啥？你不会分解质因数？

那我就赘述一下吧（手动滑稽）

我们知道，任何一个实数$n$，它的质因数均不超过$sqrt(n)$

接着我们从$2$开始枚举（$1$不是质数）

当遇到一个能被$n$整除的质数时，我们就得到了$n$的一个质因数$p$

接着，我们让$n$不断整除这个质因数，直到$n\ mod\ p \neq 0$

重复以上步骤，直至$n=1$

POJ也有这道题 （明明是先在POJ做的），听POJ的Dalao说$n=1$时要输出$0$

Tips：建议先乘再除，否则要开long long

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
using namespace std;

int n;

int read()//快读
{
	int k=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		k=k*10+c-48;
		c=getchar();
	}
	return k;
}

void fhi(int N)//
{
	int k=N;
	if(N==1)
	{
		printf("0\n");
		return;
	}
	for(int i=2;i*i<=N;++i)//分解质因数
	{
		if(N%i==0)
		{
			k=(k/i)*(i-1);//欧拉公式
			while(N%i==0)
			{
				N=N/i;
			}
		}
	}
	if(N>1)//N经过上面处理后可能会有不等于1的情况
	{
		k=(k/N)*(N-1);//欧拉公式
	}
	printf("%d\n",k);
	return;
}

int main()
{
	n=read();
	while(n!=0)
	{
		fhi(n);
		n=read();
	}
	return 0;
}

题目详见:https://www.luogu.com.cn/problem/UVA10299