oj.uz

답안 #16714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16714 2015-09-08T09:11:07 Z gs14004 Xtreme gcd sum (kriii2_X) C++14
1 / 4
 4000 ms 44688 KB 
#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 maxp = 1e6;

int che[1000005];
int moebius[1000005];
int n;

lint mod_inv(int x, int p){
	lint ret = 1, piv = x;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret;
}

void get_moebius(){
	for(int i=2; i<=maxp; i++){
		for(int j=i; j<=maxp; j+=i){
			if(!che[j]) che[j] = i;
		}
	}
	for(int i=1; i<=maxp; 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;
	}
}

vector<int> change[1000005];
int dx[1000005];
lint cnt[1000005];

int main(){
	scanf("%d",&n);
	fill(cnt, cnt + maxp + 1, 1);
	for(int i=0; i<n; i++){
		int a, b;
		scanf("%d %d",&a, &b);
		int pos = 1, cur = -1;
		int nxt_update = 1;
		while(pos <= maxp){
			cur = b / pos - (a - 1) / pos;
			nxt_update = 1e9;
			int T = b / pos - 1;
			if(T >= 0){
				int s = (b + T + 1) / (T + 1);
				if(s > pos) nxt_update = min(nxt_update, s);
			}
			T = (a - 1) / pos - 1;
			if(T >= 0){
				int s = (a + T) / (T + 1);
				if(s > pos) nxt_update = min(nxt_update, s);
			}
			nxt_update = min(nxt_update, maxp + 1);
			if(cur == 0){
				dx[pos]++;
				dx[nxt_update]--;
			}
			else{
				cnt[nxt_update] *= mod_inv(cur, mod - 2);
				cnt[pos] *= cur;
				cnt[pos] %= mod;
				cnt[nxt_update] %= mod;
			}
			pos = nxt_update;
		}
	}
	for(int i=1; i<=maxp; i++){
		cnt[i] *= cnt[i-1];
		dx[i] += dx[i-1];
		cnt[i] %= mod;
	}
	for(int i=1; i<=maxp; i++){
		if(dx[i]) cnt[i] = 0;
	}
	get_moebius();
	lint ret = 0;
	for(int i=1; i<=maxp; i++){
		for(int j=1; i*j<=maxp; j++){
			ret += 1ll * i * moebius[j] * cnt[i * j] % mod;
			ret %= mod;
		}
	}
	ret += mod;
	ret %= mod;
	printf("%lld",ret);
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 44688 KB Output is correct
2 Correct 210 ms 44688 KB Output is correct
3 Correct 212 ms 44688 KB Output is correct
4 Correct 212 ms 44688 KB Output is correct
5 Correct 214 ms 44688 KB Output is correct
6 Correct 205 ms 44688 KB Output is correct
7 Correct 207 ms 44688 KB Output is correct
8 Correct 208 ms 44688 KB Output is correct
9 Correct 208 ms 44688 KB Output is correct
10 Correct 209 ms 44688 KB Output is correct
11 Correct 212 ms 44688 KB Output is correct
12 Correct 210 ms 44688 KB Output is correct
13 Correct 216 ms 44688 KB Output is correct
14 Correct 216 ms 44688 KB Output is correct
15 Correct 209 ms 44688 KB Output is correct
16 Correct 216 ms 44688 KB Output is correct
17 Correct 213 ms 44688 KB Output is correct
18 Correct 215 ms 44688 KB Output is correct
19 Correct 209 ms 44688 KB Output is correct
20 Correct 222 ms 44688 KB Output is correct
21 Correct 212 ms 44688 KB Output is correct
22 Correct 214 ms 44688 KB Output is correct
23 Correct 219 ms 44688 KB Output is correct
24 Correct 216 ms 44688 KB Output is correct
25 Correct 214 ms 44688 KB Output is correct

Subtask #2
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 44688 KB Output is correct
2 Correct 206 ms 44688 KB Output is correct
3 Correct 217 ms 44688 KB Output is correct
4 Correct 206 ms 44688 KB Output is correct
5 Correct 206 ms 44688 KB Output is correct
6 Correct 204 ms 44688 KB Output is correct
7 Correct 213 ms 44688 KB Output is correct
8 Correct 210 ms 44688 KB Output is correct
9 Correct 216 ms 44688 KB Output is correct
10 Correct 215 ms 44688 KB Output is correct
11 Correct 755 ms 44688 KB Output is correct
12 Correct 758 ms 44688 KB Output is correct
13 Correct 764 ms 44688 KB Output is correct
14 Correct 755 ms 44688 KB Output is correct
15 Correct 759 ms 44688 KB Output is correct
16 Correct 238 ms 44688 KB Output is correct
17 Correct 248 ms 44688 KB Output is correct
18 Correct 2608 ms 44688 KB Output is correct
19 Correct 3269 ms 44688 KB Output is correct
20 Correct 2372 ms 44688 KB Output is correct
21 Correct 1307 ms 44688 KB Output is correct
22 Execution timed out 4000 ms 44684 KB Program timed out
23 Halted 0 ms 0 KB -