直接套模板，这道题貌似单独求还快一些
解法一
#include<cstdio>
#include<cctype>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 21234567;
int euler[MAXN];void get_euler()
{_for(i, 1, MAXN) euler[i] = i;_for(i, 2, MAXN)if(euler[i] == i)for(int j = i; j <= MAXN; j += i)euler[j] = euler[j] / i * (i - 1);
}void read(ll& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}int main()
{get_euler();ll n, x; read(n);while(n--){read(x);printf("%lld\n", euler[x]);}return 0;
}解法二
#include<cstdio>
#include<cctype>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 21234567;ll euler(ll x)
{ll ret = x;for(int i = 2; i * i <= x; i++)if(x % i == 0){ret = ret / i * (i - 1);while(x % i == 0) x /= i;if(x == 1) break;}if(x > 1) ret = ret / x * (x - 1);return ret;
}void read(ll& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}int main()
{ll n, x; read(n);while(n--){read(x);printf("%lld\n", euler(x));}return 0;
}