Submission #9577

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9577	2014-09-28T07:22:51 Z	veckal	Xtreme gcd sum (kriii2_X)	C++14	0 / 4	92 ms	8976 KB

X

#include<stdio.h>
const int MOD = 1000000000 + 7;

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

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 += i * num[i];
		ans %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	92 ms	8976 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-