oj.uz

Submission #8422

# Submission time Handle Problem Language Result Execution time Memory
8422 2014-09-13T18:12:02 Z ainta Xtreme gcd sum (kriii2_X) C++
0 / 4
 916 ms 20680 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, Inv[1000010];
long long Mod = 1000000007, D[1000010], Gap[1000100];
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;
	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++;
	for (i = 0; i < L; i++){
		D[Sum[i].a] = D[Sum[i].a] * Sum[i].b % Mod;
		if (i)D[Sum[i].a] = D[Sum[i].a] * Inv[Sum[i - 1].b] % Mod;
	}
}
long long Res;
void Get(){
	long long R = 1;
	int i, j;
	for (i = 1; i <= 1000000; i++){
		R = R * D[i] % Mod;
		Gap[i] = R;
	}
	for (i = 1000000; i >= 1; i--){
		for (j = i * 2; j <= 1000000; j += i){
			Gap[i] = Gap[i] - Gap[j];
			if (Gap[i] < 0)Gap[i] += Mod;
		}
		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
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 20680 KB Output is correct
2 Correct 916 ms 20680 KB Output is correct
3 Correct 908 ms 20680 KB Output is correct
4 Correct 908 ms 20680 KB Output is correct
5 Correct 908 ms 20680 KB Output is correct
6 Correct 916 ms 20680 KB Output is correct
7 Correct 904 ms 20680 KB Output is correct
8 Correct 904 ms 20680 KB Output is correct
9 Correct 912 ms 20680 KB Output is correct
10 Correct 904 ms 20680 KB Output is correct
11 Incorrect 912 ms 20680 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -