영수의 홀수 약수

1. 약수 홀수들을 구하는 것 2. 프리프로세싱하기 3. 오케이 메모이제이션 4. 배열을 활용함

#include<stdio.h> #define MAXN 13 #define ll long long ll sum[MAXN] = { 0, }; ll total[MAXN]; ll solve() { ll ret = 0; int l, r; scanf("%d %d\n", &l, &r); ret = total[r] - total[l - 1]; return ret; } void preprocess() { register int i; register int j; for (i = 1; i<MAXN; i++) { // 1부터 N까지 if (i % 2 == 1) { // 홀수 들만~ for (j = i; j<MAXN; j += i) { // j는 1부터 N까지 // j+=i 에서 걸려지는 구나 약수들이~ sum[j] += i; // 홀수 약수의 합들을 정리해 둠 } } } total[1] = sum[1]; for (i = 2; i<MAXN; i++) { total[i] = total[i - 1] + sum[i]; // 이전까지와 현재의 값들을 저장함 } } int main() { freopen("input.txt", "r", stdin); int T; int target; preprocess(); scanf("%d\n", &T); for (int t = 1; t <= T; t++) { ll ret = solve(); printf("#%d %lld\n", t, ret); } return 0; }