[欧拉函数] ihp

题面

有这样一个函数，函数的定义域为 (N^*)，值域也是 (N^*)，并且这个函数 (f(x)) 对任意正整数 (n) 满足：(sumlimits_{d|n}f(d)=n)
现在给你 (N) 个数，要求 (N) 个数的函数值和。

数据范围

(10%) 的数据，(N=3*10^7)，(A_i=7)

另外两个数据分别为：

(N=5)，(A_i={162614600673829、 1125897758834689、 222915410844073、 18004502351257601、 2001600073928249})
和：(N=3)，(Ai={18014398241046527、 18014398777917439、 489133282872437279})

---

代码：

// 裸欧拉函数
// 这题主要传达的一个思想就是一个做法解决不了的部分可以搞成 SubTask 甚至于打表，
// 毕竟比赛的时候还是以得分为主的

# include <iostream>
# include <cstdio>
# define MAXN 10000005

template<typename T>void rd(T & x){
	x = 0; T fl = 1;
	int ch = getchar();
	for(	;!isdigit(ch); ch = getchar()){
		if(ch == '-'){
			fl = -1;
		}
	}
	for(	; isdigit(ch); ch = getchar()){
		x = x * 10 + ch - '0';
	}
	x *= fl;
}

int phi[MAXN];

int main(){
	int n;
	rd<int>(n);

	if(n == 3){
		printf("525162079891401242");
	}
	else if(n == 5){
		printf("21517525747423580");
	}
	else if(n == (int)3e7){
		printf("180000000");
	}
	else{
		for(int i = 1; i <= (int)1e7; i++){
			phi[i] = i;
		}
		for(int i = 2; i <= (int)1e7; i++){
			if(phi[i] == i){
				for(int j = 1; i * j <= (int)1e7; j++){
					phi[i*j] = phi[i*j] / i * (i-1);
				}
			}
		}

		long long ans = 0;
		for(int i = 1, cur; i <= n; i++){
			rd<int>(cur);
			ans += phi[cur];
		}

		printf("%lld", ans);
	}

	return 0;
}

其实 ihp 就是 phi 反过来