Submission #9587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9587	2014-09-28T07:27:42 Z	veckal	Xtreme gcd sum (kriii2_X)	C++14	1 / 4	4000 ms	8976 KB

X

#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;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	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

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	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	-