Submission #16698

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
16698	2015-09-08T07:54:39 Z	gs14004	Xtreme gcd sum (kriii2_X)	C++14	1 / 4	4000 ms	17424 KB

X

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int rng = 1e6;

int che[1000005];
int moebius[1000005];
int n, a[10005], b[10005];
lint cnt[1000005];

lint get(int x){
	lint ret = 1;
	for(int i=0; i<n; i++){
		ret *= b[i] / x - (a[i] - 1) / x;
		ret %= mod;
	}
	return ret;
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i], &b[i]);
	}
	for(int i=2; i<=1000000; i++){
		for(int j=i; j<=rng; j+=i){
			if(!che[j]) che[j] = i;
		}
	}
	for(int i=1; i<=rng; i++){
		int cnt = 0, lst = -1;
		int x = i;
		while(x > 1){
			if(lst == che[x]){
				cnt = -1;
				break;
			}
			lst = che[x];
			x /= lst;
			cnt++;
		}
		if(cnt < 0) continue;
		moebius[i] = cnt % 2 ? -1 : 1;
	}
	for(int i=1; i<=rng; i++){
		cnt[i] = get(i);
	}
	lint ret = 0;
	for(int i=1; i<=rng; i++){
		for(int j=1; i*j<=rng; j++){
			ret += 1ll * i * moebius[j] * cnt[i * j] % mod;
			ret %= mod;
		}
	}
	printf("%lld",ret);
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	216 ms	17424 KB	Output is correct
2	Correct	217 ms	17424 KB	Output is correct
3	Correct	212 ms	17424 KB	Output is correct
4	Correct	226 ms	17424 KB	Output is correct
5	Correct	230 ms	17424 KB	Output is correct
6	Correct	226 ms	17424 KB	Output is correct
7	Correct	229 ms	17424 KB	Output is correct
8	Correct	238 ms	17424 KB	Output is correct
9	Correct	238 ms	17424 KB	Output is correct
10	Correct	240 ms	17424 KB	Output is correct
11	Correct	320 ms	17424 KB	Output is correct
12	Correct	313 ms	17424 KB	Output is correct
13	Correct	307 ms	17424 KB	Output is correct
14	Correct	314 ms	17424 KB	Output is correct
15	Correct	308 ms	17424 KB	Output is correct
16	Correct	307 ms	17424 KB	Output is correct
17	Correct	315 ms	17424 KB	Output is correct
18	Correct	326 ms	17424 KB	Output is correct
19	Correct	309 ms	17424 KB	Output is correct
20	Correct	307 ms	17424 KB	Output is correct
21	Correct	323 ms	17424 KB	Output is correct
22	Correct	307 ms	17424 KB	Output is correct
23	Correct	308 ms	17424 KB	Output is correct
24	Correct	307 ms	17424 KB	Output is correct
25	Correct	307 ms	17424 KB	Output is correct

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1326 ms	17424 KB	Output is correct
2	Correct	1329 ms	17424 KB	Output is correct
3	Correct	1320 ms	17424 KB	Output is correct
4	Correct	1323 ms	17424 KB	Output is correct
5	Correct	1339 ms	17424 KB	Output is correct
6	Correct	1328 ms	17424 KB	Output is correct
7	Correct	1332 ms	17424 KB	Output is correct
8	Correct	1334 ms	17424 KB	Output is correct
9	Correct	1333 ms	17424 KB	Output is correct
10	Correct	1328 ms	17424 KB	Output is correct
11	Execution timed out	4000 ms	17420 KB	Program timed out
12	Halted	0 ms	0 KB	-