LightOJ - 1370（欧拉公式）

也就是欧拉公式板子题吧

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 10;

ll phi[MAXN + 1];
void euler(int n) {
	for(int i = 2; 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[j] / i * (i - 1);
			}
		}
	}
}
int main () {
	euler(MAXN);
	int T;
	scanf("%d", &T);
	int n;
	int i = 0;
	while(T--) {
		scanf("%d", &n);
		ll ans = 0;
		while(n--) {
			ll x;
			scanf("%lld", &x);
			ll temp = x + 1;
			while(phi[temp] < x) {
				temp++;
			}
			ans += temp;
		}
		printf("Case %d: %lld Xukha\n", ++i, ans);
	}
}

数论基础题

原文：https://www.cnblogs.com/lightac/p/14185907.html