蓝桥杯算法提高VIP-欧拉函数 （C++代码）

解题思路:
        

        题目我看的云里雾里，欧拉函数我之前用到过，用来计算某个 N 作为分母时它的真分子的个数，就是这个式子。

        我们来发散一下题目：

    例如： 20 = 2 * 2 * 5， 那么 20 的真分子数就是 20 * ( 1 - 1/2 ) * ( 1 - 1/5 ) = 8，所以 20 
 
作为分母它的真分子个数有 8 个，
 
    在举一个: 25 = 5 * 5, 它的真分子个数为 25 * （1 - 1/5） = 20 个，
 
    式子换个方式表示就是 phi(20) = 20 * （ 1/2 ）*（ 4/5 ） = 8， phi(30) = 30 * （ 1/2 ） 

* （ 2/3 ） * （4/5）= 8，（因为 30 = 2 * 3 * 5）,同理 phi(17) = 16，
     
    而这个结果就是题目所求的欧拉函数的值，从以上例子可以看到，只要求出最简的因子，再把

不重复因子代入算式即可得到结果。( 不取 1 ，不然得到的值都是 0 )

参考代码:

#include<iostream>
using namespace std;

	/*			  分解因子  			  */
int findFact(long long num, int arr[]) {
	int total = 0;

	for (int i = 2; i <= num; i++)
		while (num % i == 0) {
			arr[total++] = i;
			num /= i;
		}

	return total;
}

long long euler_Function(long long n) {
	if (n == 1) return 0;

	/*			total是因子个数				*/
	int fact[10], total = findFact(n, fact);

	long long phi = n;
	/*			  不计重复因子   		   */
	for (int i = 0; i < total; i++)
		if (fact[i] != fact[i + 1])
			phi = phi / fact[i] * (fact[i] - 1);

	return phi;
}

int main() {
	int n;
	cin >> n;
	cout << euler_Function(n);
	return 0;
}