Submission #8430

#	Time	Username	Problem	Language	Result	Execution time	Memory
8430		ainta	Xtreme gcd sum (kriii2_X)	C++98	4 / 4	2276 ms	24524 KiB

X

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, Inv[1000010];
long long Mod = 1000000007, D[1000010], Gap[1000100], Res;
int Chk[1000010];
long long Pow(long long a, int x){
	long long r = 1;
	while (x){
		if (x & 1)r = r*a%Mod;
		a = a*a%Mod;
		x >>= 1;
	}
	return r;
}
int Next(int a, int m){
	if (!a)return 999999999;
	return m / a + 1;
}
int main()
{
	int i, j, a, b, pv, t, t2;
	long long G;
	scanf("%d", &n);
	for (i = 1; i <= 1000000; i++){
		Inv[i] = Pow(i, Mod - 2);
		D[i] = 1;
	}
	for (i = 1; i <= n; i++){
		scanf("%d%d", &a, &b);
		a--;
		pv = 1;
		t = 1;
		while (pv <= b){
			t2 = b / pv - a / pv;
			if (t2 == 0)Chk[pv]++;
			else{
				D[pv] = D[pv] * t2 % Mod;
				D[pv] = D[pv] * Inv[t] % Mod;
				t = t2;
			}
			pv = min(Next(a / pv, a), Next(b / pv, b));
			if (t2 == 0)Chk[pv]--;
		}
		D[b + 1] = 0;
	}
	G = 1;
	for (i = 1; i <= 1000000; i++){
		Chk[i] += Chk[i - 1];
		G = G * D[i] % Mod;
		if (!Chk[i])Gap[i] = G;
	}
	for (i = 1000000; i >= 1; i--){
		if (Chk[i])continue;
		G = Gap[i];
		for (j = i + i; j <= 1000000; j+=i){
			G = G - Gap[j];
			if (G < 0)G += Mod;
		}
		Gap[i] = G;
		Res = (Res + Gap[i] * i) % Mod;
	}
	printf("%lld\n", Res);
}

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