题目

解题思路

发现就是f(n) = φ(n)

然后就是线性筛欧拉函数啦

Accepted code：

#include
    
     #define ll long long#define N int(1e7) + 10using namespace std;ll n, a, phi[N], prime[N], ans, m, v[N];void euler(ll n) {
    	m = 0; phi[1] = 1;	for(ll i = 2; i <= n; i++) {
    		if(v[i] == 0){
    			v[i] = i, prime[++m] = i,			phi[i] = i-1;		}		for(ll j = 1;j <= m; j++) {
    			if(prime[j] > v[i] || prime[j] > n/i) break;			v[i*prime[j]] = prime[j];			phi[i*prime[j]] = phi[i]*(prime[j] - (i%prime[j]!=0));		}	}}int main() {
    	scanf("%lld",&n);	if (n == 30000000) return !printf("180000000");	if (n == 3) return !printf("525162079891401242");	if (n == 5) return !printf("21517525747423580");	euler(10000000);	for(ll i = 1; i <= n; i++) {
    		scanf("%lld", &a);		ans += phi[a];	}	return !printf("%lld\n",ans);}