c语言实现欧拉函数,欧拉Euler函数

/*

________ _ ________ _

/ ______| | | | __ | | |

/ / | | | |__| | | |

| | | |___ _ _ _ ___ _ _____ | ___| ______ _____ ___ _ | |

| | | __ \\ |_| | | | | | _\\| | | ____| | |\\ \\ | __ | | _ | | _\\| | | |

| | | | \\ | _ | | | | | | \\ | | \\___ | | \\ \\ | |_/ _| | |_| | | | \\ | | |

\\ \\______ | | | | | | \\ |_| / | |_/ | ___/ | | | \\ \\ | /_ \\__ | | |_/ | | |

Author : \\________| |_| |_| |_| \\___/ |___/|_| |_____| _________|__| \\__\\ |______| | | |___/|_| |_|

____| |

\\_____/

*/

//#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#define G 10.0

#define LNF 1e18

#define EPS 1e-6

#define PI acos(-1.0)

#define INF 0x7FFFFFFF

#define ll long long

#define ull unsigned long long

#define LOWBIT(x) ((x) & (-x))

#define LOWBD(a, x) lower_bound(a.begin(), a.end(), x) - a.begin()

#define UPPBD(a, x) upper_bound(a.begin(), a.end(), x) - a.begin()

#define TEST(a) cout << "---------" << a << "---------" << '\\n'

#define CHIVAS int main()

#define _REGAL exit(0)

#define SP system("pause")

#define IOS ios::sync_with_stdio(false)

//#define map unordered_map

#define PB(x) push_back(x)

#define ALL(a) ((a).begin(),(a).end())

#define MEM(a, b) memset(a, b, sizeof(a))

#define EACH_CASE(cass) for (scanf("%d", &cass); cass; cass--)

#define LS l, mid, rt << 1

#define RS mid + 1, r, rt << 1 | 1

#define GETMID (l + r) >> 1

using namespace std;

template inline T MAX(T a, T b){return a > b? a : b;}

template inline T MIN(T a, T b){return a > b? b : a;}

template inline void SWAP(T &a, T &b){T tp = a; a = b; b = tp;}

template inline T GCD(T a, T b){return b > 0? gcd(b, a % b) : a;}

template inline void ADD_TO_VEC_int(T &n, vector &vec){vec.clear(); cin >> n; for(int i = 0; i < n; i ++){T x; cin >> x, vec.PB(x);}}

template inline pair MaxInVector_ll(vector vec){T MaxVal = -LNF, MaxId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MaxVal < vec[i]) MaxVal = vec[i], MaxId = i; return {MaxVal, MaxId};}

template inline pair MinInVector_ll(vector vec){T MinVal = LNF, MinId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MinVal > vec[i]) MinVal = vec[i], MinId = i; return {MinVal, MinId};}

template inline pair MaxInVector_int(vector vec){T MaxVal = -INF, MaxId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MaxVal < vec[i]) MaxVal = vec[i], MaxId = i; return {MaxVal, MaxId};}

template inline pair MinInVector_int(vector vec){T MinVal = INF, MinId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MinVal > vec[i]) MinVal = vec[i], MinId = i; return {MinVal, MinId};}

//template inline pair, vector > DIV(T n){T nn = n;map cnt;vector div;for(ll i = 2; i * i <= nn; i ++){while(n % i == 0){if(!cnt[i]) div.push_back(i);cnt[i] ++;n /= i;}}if(n != 1){if(!cnt[n]) div.push_back(n);cnt[n] ++;n /= n;}return {cnt, div};}

const int maxn = 400005;

int phi[maxn];

int n;

inline void GET_PHI(){

for(int i = 0; i <= n; i ++) phi[i] = i;

for(int i = 2; i <= n; i ++){

if(phi[i] == i){

for(int j = i; j <= n; j += i) phi[j] = phi