备战NOIP——模板复习20

这里只有模板，并不作讲解，仅为路过的各位做一个参考以及用做自己复习的资料，转载注明出处。

线性筛求欧拉函数

/*Copyright: Copyright (c) 2018
*Created on 2018-11-05
*Author: 十甫
*Version 1.0 
*Title: 线性筛求欧拉函数
*Time: inf mins
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int size = 50050;

int phi[size], prime[size];
bool vis[size];

inline void make(int n) {
	phi[1] = 1;
	for(int i = 2;i <= n;i++) {
		if(!vis[i]) {
			prime[++prime[0]] = i;
			phi[i] = i - 1;
		}
		for(int j = 1;j <= prime[0] && prime[j] * i <= n;j++) {
			vis[prime[j] * i] = true;
			if(!(i % prime[j])) {
				phi[prime[j] * i] = phi[i] * prime[j];
				break;
			} else {
				phi[prime[j] * i] = phi[i] * phi[prime[j]];
			}
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	make(n);
	int m;
	scanf("%d", &m);
	while(m--) {
		int k;
		scanf("%d", &k);
		printf("%d
", phi[k]);
	}
	return 0;
}