답안 #9587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9587 2014-09-28T07:27:42 Z veckal Xtreme gcd sum (kriii2_X) C++14
1 / 4
4000 ms 8976 KB
#include<stdio.h>
const int MOD = 1000000000 + 7;

int n, a[10000], b[10000];
long long num[1000001];

int main() {
	scanf("%d", &n);
	for (int i=0;i<n; ++i)
		scanf("%d%d", a+i, b+i);
	long long ans = 0;
	for (int i=1000000; i>0; --i) {
		num[i] = 1;
		for (int j=0; j<n; ++j) {
			num[i] *= b[j]/i - (a[j]-1)/i;
			num[i] %= MOD;
		}
		for (int j=i+i; j<=1000000; j+=i) {
			num[i] -= num[j];
			if (num[i] < 0) num[i] += MOD;
		}
		ans += num[i] * i;
		ans %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 8976 KB Output is correct
2 Correct 92 ms 8976 KB Output is correct
3 Correct 100 ms 8976 KB Output is correct
4 Correct 108 ms 8976 KB Output is correct
5 Correct 108 ms 8976 KB Output is correct
6 Correct 108 ms 8976 KB Output is correct
7 Correct 124 ms 8976 KB Output is correct
8 Correct 120 ms 8976 KB Output is correct
9 Correct 124 ms 8976 KB Output is correct
10 Correct 124 ms 8976 KB Output is correct
11 Correct 200 ms 8976 KB Output is correct
12 Correct 192 ms 8976 KB Output is correct
13 Correct 192 ms 8976 KB Output is correct
14 Correct 196 ms 8976 KB Output is correct
15 Correct 192 ms 8976 KB Output is correct
16 Correct 192 ms 8976 KB Output is correct
17 Correct 184 ms 8976 KB Output is correct
18 Correct 200 ms 8976 KB Output is correct
19 Correct 192 ms 8976 KB Output is correct
20 Correct 188 ms 8976 KB Output is correct
21 Correct 204 ms 8976 KB Output is correct
22 Correct 196 ms 8976 KB Output is correct
23 Correct 184 ms 8976 KB Output is correct
24 Correct 196 ms 8976 KB Output is correct
25 Correct 196 ms 8976 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1180 ms 8976 KB Output is correct
2 Correct 1180 ms 8976 KB Output is correct
3 Correct 1180 ms 8976 KB Output is correct
4 Correct 1176 ms 8976 KB Output is correct
5 Correct 1184 ms 8976 KB Output is correct
6 Correct 1172 ms 8976 KB Output is correct
7 Correct 1180 ms 8976 KB Output is correct
8 Correct 1184 ms 8976 KB Output is correct
9 Correct 1180 ms 8976 KB Output is correct
10 Correct 1180 ms 8976 KB Output is correct
11 Execution timed out 4000 ms 8972 KB Program timed out
12 Halted 0 ms 0 KB -