コドフォ Educational Contst 89 D. Two Divisors 解説[python]
ジャンル
パズル、整数問題、構築
概要
整数nが与えられ、それの1以上の約数の組のうち、gcd(a+b, n) = 1となる組を１つ出力せよ。
ない場合は-1を出せ
制約
1<=n<=5*10**5 クエリの個数
2<=ai<=10**7 整数nの大きさ
考察
約数の個数は10**7なら高々200個程度なので全探索でもいける?
(ただ、クエリの個数が大きいのでそれに200C2 を重ねると無理そう)
探索する範囲を絞ることを考えると、明らかに、a,b が同じ公約数を持っていた場合は無理でa,bは互いに素である
n を素因数分解して、良さげな性質を見つけたい
nの一番小さい素数と、nのそれ以外の素数の積を考えると、nの一番小さい素数 とnのそれ以外の素数の積は互いに素だから この和はnの一番小さい素数 では割り切れず、かつ、nのそれ以外の素数よりも足された数は小さいからそれでも割り切れない。
よってこれが条件を満たす。
-1になるケースは素数を1種類しか持たない時
実装
TLE解2
事前計算して素因数の列挙することを高速化することを考える。
10**7までの値の素因数は10**7以下になるので、10**7以下の素数をエラトステネスで全列挙した後にそれらで割っていくことを考える。
C++ だとこれで通るらしいが、Python(Pypy)だとTLE(test case 23)
import sys import math N = 10 ** 7 def eratosthenes(N): prime = [] table = [0] * (N + 1) for i in range(2, N + 1): if table[i]: continue prime.append(i) for j in range(i, N + 1, i): table[j] = 1 # print(prime) return prime read = sys.stdin.buffer.read input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines n = int(input()) a = list(map(int, input().split())) ans_u = [0] * n ans_b = [0] * n prime = eratosthenes(N) # print(len(prime) / 10 ** 7 * 100) 6.6%が素数 cnt = 0 for i in a: ng = 1 for j in prime: if j ** 2 > i: break if i % j == 0: while i % j == 0: i = i // j if i == 1: break ans_b[cnt] = i ans_u[cnt] = j ng = 0 break if ng: ans_b[cnt] = -1 ans_u[cnt] = -1 cnt += 1 print(*ans_u) print(*ans_b)
さらに高速化することを考える。
現在の計算量は
エラトステネスの篩 でO(NlogN) N=10**7
各要素に関して最小の素因数で割っていく
O(NKlogA)
K: root(A)以下の素数の数(root(10**7) 以下の素数は400 個くらい。
N : クエリの個数 5*10**5
logA : 最小の素数で何回われるか？log 10**7 で底が2でも高々25以下
よって、計算量が10**8 オーダーになって落ちる。
AC解
Kを最小の素数を見つける箇所を無くしたい。事前計算時に効率化することを考える。
事前計算（エラトステネスの篩の時に）10**7までの値のテーブルを作っているので、それぞれの値に対して、約数としてもつ素数を1ついれておくことを考える。
計算量はO(NlogA) で10**7 オーダー
実行時間は1341msec なのでギリギリ。
定数倍高速化を狙うと、最小の素数でなくて、できるだけ大きい素数にするとlogAの底が大きくなるので早くなりそう。
import sys import math N = 10 ** 7 table = [0] * (N + 1) def eratosthenes(N): prime = [] table[0] = 0 table[1] = 1 for i in range(2, N + 1): if table[i]: continue prime.append(i) for j in range(i, N + 1, i): table[j] = i # print(prime) return prime read = sys.stdin.buffer.read input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines n = int(input()) a = list(map(int, input().split())) ans_u = [0] * n ans_b = [0] * n prime = eratosthenes(N) # print(len(prime)) # 6.6%が素数 cnt = 0 for i in a: # talbe[i] がi が持つ最小の素数 # table[i]でi を割り切れるまでわる min_prime = table[i] # print(i, min_prime) while i % min_prime == 0: i = i // min_prime if i != 1: # 素数を2種類以上持つ ans_b[cnt] = i ans_u[cnt] = min_prime else: ans_b[cnt] = -1 ans_u[cnt] = -1 cnt += 1 print(*ans_u) print(*ans_b)
