|poj 2478|欧拉函数|Farey Sequence

poj传送门 筛选法求欧拉函数

每个询问答案是

∑i=1nφ(i)

#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ms(i,j) memset(i,j, sizeof i); using namespace std; #define ll long long ll phi[1000000+5]; void phitable(ll n) { for (int i=2;i<=n;i++) phi[i] = 0; phi[1] = 1; for (int i=2;i<=n;i++) if (!phi[i]) for (int j=i;j<=n;j+=i) { if (!phi[j]) phi[j] = j; phi[j] = phi[j]/i*(i-1); } } int main() { phitable(1000000); int n; while (scanf("%d", &n)==1 && n) { ll tot = 0; for (int i=2;i<=n;i++) tot += phi[i]; printf("%lld\n", tot); } return 0; }