算法基础之欧拉函数

欧拉函数

• 核心思想：欧拉函数:

  • 证明 ：容斥原理

    •   #include<iostream>
        #include<algorithm>
        
        using namespace std;
        const int N = 110;
        
        int main()
        {
            int n;
            cin>>n;
            while(n--)
            {
                int a;
                cin>>a;
                
                int res = a;
                for(int i =2;i <= a/i; i++)
                {
                    if(a % i == 0)  //找到因数i
                    {
                        res = res /i * (i-1) ;  //乘一次
                        while(a % i == 0) a/=i;  //求另外一个因数  因为公式不管a次方 只要知道因数是多少就行
                    }
                }
                
                if(a >1) res = res / a *(a - 1);  //另一个因数a存在 也乘
                
                cout<<res<<endl;
            }
        }