파이의 합 아메리칸 조식

1. 수식을 보고 2. 그대로 구현 하는 능력 3. 오케이 4. 파이를 어떻게 풀이 할 것인가 5. 소수를 구하는 에라토스테네스의 체

#include <stdio.h> const int MAXN = 35; int PHI[MAXN + 1]; long long PHI_SUM[MAXN + 1]; int tc, T, a, b; int main(void) { freopen("input.txt", "r", stdin); PHI[1] = 1, PHI_SUM[1] = 1; for (int i = 2; i <= MAXN; ++i) { if (PHI[i] == 0) { PHI[i] = i - 1; // 아 여기서, 그냥 풀이가 됨. 분자는 분모에서 하나 빼는 것 for (int j = i + i; j <= MAXN; j += i) // { if (PHI[j] == 0) PHI[j] = j; // 주어진 수식 풀이 PHI[j] /= i; // 일단 나누고, PHI[j] *= PHI[i]; // 이것을 곱하면 됨 } } PHI_SUM[i] = PHI_SUM[i - 1] + PHI[i]; } for (tc = scanf("%d", &T); tc <= T; ++tc) { scanf("%d%d", &a, &b); printf("#%d %lld\n", tc, PHI_SUM[b] - PHI_SUM[a - 1]); } return 0; }