프양연 파이의 합 / 서로소 2중 포문

1. 서로소, 최대공약수, 최소공배수 정리 필요 2. 수식 이해 2중 포문 끝

#include <stdio.h> //const int MAXN = 1000000; const int MAXN = 100; 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, k = 2; j <= MAXN; j += i, ++k) { 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; }