Submission #9454

#	Time	Username	Problem	Language	Result	Execution time	Memory
9454		lemonsqueeze	Xtreme gcd sum (kriii2_X)	C++98	1 / 4	4000 ms	16868 KiB

X

#include <cstdio>

const int N = 10000;
const int NUMERIC = 2000000;
typedef long long int64;

const int64 MOD = 1000000007;

int n;
int64 a[N], b[N], d[NUMERIC];

int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld %lld", &a[i], &b[i]);
	for (int i = 1000000; i >= 1; i--) {
		int64 cnt = 1;
		for (int j = 0; j < n; j++) {
			int bdiv = b[j] / i;
			int adiv = (a[j] - 1) / i;
			int64 tmpcnt = (bdiv - adiv);
			cnt = (cnt * tmpcnt) % MOD;
		}
		d[i] = cnt;
		for (int j = i + i; j <= 1000000; j+=i) {
			d[i] = (d[i] - d[j] + MOD) % MOD;
		}
	}
	int64 ans = 0;
	for (int i = 1; i <= 1000000; i++) {
		ans += (int64) i * d[i];
		ans = ans % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 3