题目描述

欧拉函数
略

样例

#include <iostream>

using namespace std;

int main()
{
    int n=0,a=0,res;
    cin>>n;
    while ( n-- )
    {
        cin>> a;
        res=a;
        for (int i = 2; i <= a/i; i ++ )
        {
            if(a%i == 0)
            {
                res=res/i*(i-1);  //先除再乘，防止越界。能如此操作的原因是i为res的因子
                while (a%i == 0) a/=i;
            }
        }
        if ( a!=1 ) res=res/a*(a-1);
        cout<< res<< '\n';
    }
}