M5 - 欧拉筛

bool ar[maxn >> 1u];
int phi[maxn >> 1u];
vector< int > prs;

inline int lowbit(const int x) { return -x & x; }

void sieve(const int n) {
	prs.reserve(n / log(n) * 1.2);
	phi[1 >> 1u] = 1;
	for (int i = 3; i <= n; i += 2) {
		if (!ar[i >> 1u]) {
			prs.push_back(i);
			phi[i >> 1u] = i - 1;
		}
		for (int j = 0, des = n / i, k; prs[j] <= des; j++) {
			ar[k = (prs[j] * i >> 1u)] = true;
			if (i % prs[j] == 0) {
				phi[k] = prs[j] * phi[i >> 1u];
				break;
			} else phi[k] = phi[prs[j] >> 1u] * phi[i >> 1u];
		}
	}
}

int euler(const int n) {
	if (n & 1u) return phi[n >> 1u];
	else return phi[n / lowbit(n) >> 1u] * lowbit(n) >> 1u;
}