Submission #8430

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
8430	2014-09-13T18:50:10 Z	ainta	Xtreme gcd sum (kriii2_X)	C++	4 / 4	2276 ms	24524 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], 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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	916 ms	24524 KB	Output is correct
2	Correct	912 ms	24524 KB	Output is correct
3	Correct	912 ms	24524 KB	Output is correct
4	Correct	920 ms	24524 KB	Output is correct
5	Correct	916 ms	24524 KB	Output is correct
6	Correct	912 ms	24524 KB	Output is correct
7	Correct	924 ms	24524 KB	Output is correct
8	Correct	904 ms	24524 KB	Output is correct
9	Correct	920 ms	24524 KB	Output is correct
10	Correct	916 ms	24524 KB	Output is correct
11	Correct	924 ms	24524 KB	Output is correct
12	Correct	924 ms	24524 KB	Output is correct
13	Correct	924 ms	24524 KB	Output is correct
14	Correct	916 ms	24524 KB	Output is correct
15	Correct	916 ms	24524 KB	Output is correct
16	Correct	908 ms	24524 KB	Output is correct
17	Correct	888 ms	24524 KB	Output is correct
18	Correct	884 ms	24524 KB	Output is correct
19	Correct	920 ms	24524 KB	Output is correct
20	Correct	916 ms	24524 KB	Output is correct
21	Correct	888 ms	24524 KB	Output is correct
22	Correct	916 ms	24524 KB	Output is correct
23	Correct	920 ms	24524 KB	Output is correct
24	Correct	920 ms	24524 KB	Output is correct
25	Correct	924 ms	24524 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	908 ms	24524 KB	Output is correct
2	Correct	912 ms	24524 KB	Output is correct
3	Correct	912 ms	24524 KB	Output is correct
4	Correct	908 ms	24524 KB	Output is correct
5	Correct	920 ms	24524 KB	Output is correct
6	Correct	916 ms	24524 KB	Output is correct
7	Correct	920 ms	24524 KB	Output is correct
8	Correct	912 ms	24524 KB	Output is correct
9	Correct	916 ms	24524 KB	Output is correct
10	Correct	908 ms	24524 KB	Output is correct
11	Correct	1056 ms	24524 KB	Output is correct
12	Correct	1060 ms	24524 KB	Output is correct
13	Correct	1048 ms	24524 KB	Output is correct
14	Correct	1064 ms	24524 KB	Output is correct
15	Correct	1052 ms	24524 KB	Output is correct
16	Correct	888 ms	24524 KB	Output is correct
17	Correct	892 ms	24524 KB	Output is correct
18	Correct	1480 ms	24524 KB	Output is correct
19	Correct	1672 ms	24524 KB	Output is correct
20	Correct	1396 ms	24524 KB	Output is correct
21	Correct	1188 ms	24524 KB	Output is correct
22	Correct	2168 ms	24524 KB	Output is correct
23	Correct	2276 ms	24524 KB	Output is correct
24	Correct	1884 ms	24524 KB	Output is correct
25	Correct	1876 ms	24524 KB	Output is correct