Submission #9587

#	Time	Username	Problem	Language	Result	Execution time	Memory
9587		veckal	Xtreme gcd sum (kriii2_X)	C++14	1 / 4	4000 ms	8976 KiB

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 / 1
• Subtask 2: 0 / 3