답안 #8428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8428	2014-09-13T18:27:11 Z	ainta	Xtreme gcd sum (kriii2_X)	C++	4 / 4	1892 ms	24588 KB

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.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	912 ms	24588 KB	Output is correct
2	Correct	892 ms	24588 KB	Output is correct
3	Correct	916 ms	24588 KB	Output is correct
4	Correct	892 ms	24588 KB	Output is correct
5	Correct	908 ms	24588 KB	Output is correct
6	Correct	908 ms	24588 KB	Output is correct
7	Correct	904 ms	24588 KB	Output is correct
8	Correct	916 ms	24588 KB	Output is correct
9	Correct	916 ms	24588 KB	Output is correct
10	Correct	916 ms	24588 KB	Output is correct
11	Correct	920 ms	24588 KB	Output is correct
12	Correct	916 ms	24588 KB	Output is correct
13	Correct	920 ms	24588 KB	Output is correct
14	Correct	920 ms	24588 KB	Output is correct
15	Correct	924 ms	24588 KB	Output is correct
16	Correct	896 ms	24588 KB	Output is correct
17	Correct	896 ms	24588 KB	Output is correct
18	Correct	888 ms	24588 KB	Output is correct
19	Correct	916 ms	24588 KB	Output is correct
20	Correct	908 ms	24588 KB	Output is correct
21	Correct	904 ms	24588 KB	Output is correct
22	Correct	916 ms	24588 KB	Output is correct
23	Correct	920 ms	24588 KB	Output is correct
24	Correct	908 ms	24588 KB	Output is correct
25	Correct	912 ms	24588 KB	Output is correct

Subtask #2

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	916 ms	24588 KB	Output is correct
2	Correct	904 ms	24588 KB	Output is correct
3	Correct	912 ms	24588 KB	Output is correct
4	Correct	908 ms	24588 KB	Output is correct
5	Correct	912 ms	24588 KB	Output is correct
6	Correct	892 ms	24588 KB	Output is correct
7	Correct	912 ms	24588 KB	Output is correct
8	Correct	908 ms	24588 KB	Output is correct
9	Correct	916 ms	24588 KB	Output is correct
10	Correct	908 ms	24588 KB	Output is correct
11	Correct	1052 ms	24588 KB	Output is correct
12	Correct	1044 ms	24588 KB	Output is correct
13	Correct	1036 ms	24588 KB	Output is correct
14	Correct	1040 ms	24588 KB	Output is correct
15	Correct	1048 ms	24588 KB	Output is correct
16	Correct	896 ms	24588 KB	Output is correct
17	Correct	896 ms	24588 KB	Output is correct
18	Correct	1384 ms	24588 KB	Output is correct
19	Correct	1452 ms	24588 KB	Output is correct
20	Correct	1272 ms	24588 KB	Output is correct
21	Correct	1120 ms	24588 KB	Output is correct
22	Correct	1792 ms	24588 KB	Output is correct
23	Correct	1892 ms	24588 KB	Output is correct
24	Correct	1660 ms	24588 KB	Output is correct
25	Correct	1676 ms	24588 KB	Output is correct