CodeForces 75 C Modified GCD【二分+数論】
1410 ワード
タイトルリンク
まずaとbの最大公約数を求め,そのすべての因数であるsqrt(n)の複雑さを探し出し,姿勢を上げた.
そして、すべての因数がlow、high区間に落ちているかどうかを判断します.2点でいいです(upper_bound)
C++バージョン:
Pythonバージョン:
まずaとbの最大公約数を求め,そのすべての因数であるsqrt(n)の複雑さを探し出し,姿勢を上げた.
そして、すべての因数がlow、high区間に落ちているかどうかを判断します.2点でいいです(upper_bound)
C++バージョン:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
vector<int> x;
int low, high, a, b, n, m, ans;
int main() {
scanf("%d%d", &a, &b);
a = __gcd(a, b);
b = sqrt(a);
x.clear();
for (int i=1; i<=b; i++)
if (a % i == 0) {
x.push_back(i);
x.push_back(a/i);
}
sort(x.begin(), x.end());
scanf("%d", &n);
for (int i=0; i<n; i++) {
scanf("%d%d", &low, &high);
m = upper_bound(x.begin(), x.end(), high) - x.begin() - 1;
ans = x[m];
if (low > ans) puts("-1");
else printf("%d
", ans);
}
return 0;
}
Pythonバージョン:
from fractions import gcd
from bisect import bisect_right as br
g = gcd(*map(int, raw_input().split()))
i = 1
r = []
while i*i <= g:
if g % i == 0:
r.append(i)
r.append(g/i)
i += 1
r = sorted(r)
for i in xrange(input()):
l, h = map(int, raw_input().split())
m = r[br(r, h)-1]
print -1 if m < l else m