Submission #8428

#	Time	Username	Problem	Language	Result	Execution time	Memory
8428		ainta	Xtreme gcd sum (kriii2_X)	C++98	4 / 4	1892 ms	24588 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];
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;
}
struct A{
	int a, b;
}S[2][2010], Sum[4010];
int Len[2];
void Ins(int pv, int a, int b){
	S[pv][Len[pv]].a = a;
	S[pv][Len[pv]].b = b;
	Len[pv]++;
}
void Do(int pv, int a){
	int i, t = 1;
	Len[pv] = 0;
	for (i = 1; i*i <= a; i++){
		Ins(pv, i, a / i);
		t = a / i;
	}
	for (i = t - 1; i >= 0; i--){
		Ins(pv, a / (i + 1) + 1, i);
	}
}
void Pro(){
	int i, pv1 = 0, pv2 = 0, L = 0, t;
	while (pv1 != Len[0] - 1 || pv2 != Len[1] - 1){
		Sum[L].a = max(S[1][pv2].a, S[0][pv1].a);
		Sum[L].b = S[1][pv2].b - S[0][pv1].b;
		L++;
		if (pv1 == Len[0] - 1)pv2++;
		else if (pv2 == Len[1] - 1)pv1++;
		else{
			if (S[0][pv1 + 1].a < S[1][pv2 + 1].a)pv1++;
			else pv2++;
		}
	}
	Sum[L].a = max(S[0][pv1].a, S[1][pv2].a);
	Sum[L].b = 0; L++;
	t = -1;
	for (i = 0; i < L; i++){
		if (i != L - 1 && Sum[i].a == Sum[i + 1].a)continue;
		if (Sum[i].b == 0 && i != L - 1){
			Chk[Sum[i].a]++;
			Chk[Sum[i + 1].a]--;
			continue;
		}
		D[Sum[i].a] = D[Sum[i].a] * Sum[i].b % Mod;
		if (t != -1)D[Sum[i].a] = D[Sum[i].a] * Inv[t] % Mod;
		t = Sum[i].b;
	}
}
long long Res;
void Get(){
	long long R = 1;
	int i, j, c = 0;
	for (i = 1; i <= 1000000; i++){
		R = R * D[i] % Mod;
		Gap[i] = R;
		Chk[i] += Chk[i - 1];
		if (Chk[i])Gap[i] = 0;
	}
	for (i = 1000000; i >= 1; i--){
		if (Chk[i])continue;
		for (j = i * 2; j <= 1000000; j += i){
			Gap[i] = Gap[i] - Gap[j];
			if (Gap[i] < 0)Gap[i] += Mod;
		}
		Res = (Res + Gap[i] * i) % Mod;
	}
}
int main()
{
	int i, j, a, b;
	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);
		Do(0, a - 1);
		Do(1, b);
		Pro();
	}
	Get();
	printf("%lld\n", Res);
}

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