NTL_1_B: Power
べき乗
10^9乗なんてまともにやると大変なので
m^2n = m^n * m^nという関係を使ってlog nのオーダにしてやる
余りを求めろとなってるのは
a * b % q == (a % q) * (b % q)だから毎回余りをとってやればよかろう
1000000007で割るというのは32ビットで収まるように、
いや2乗しても64ビットに収まるように、ってことかな
def power(m, n):
if n == 0:
return 1
elif n % 2 == 0:
k = power(m, n // 2)
return k * k % 1000000007
else:
k = power(m, (n - 1) // 2)
return k * k * m % 1000000007
m, n = [int(x) for x in input().split()]
print(power(m, n))いったんpower(m, n // 2)を変数に入れてやるのが大事
うっかりreturn power(m, n // 2) * power(m, n // 2)とか書いてしまうと
nのオーダになってしまう
ALDS1_1_B: Greatest Common Divisor
最大公約数と言えば互除法
x, y = [int(x) for x in input().split()]
while x % y != 0:
x, y = y, x % y
print(y)一時変数を使わなくても変数を入れ替えられるのがうれしい
続きを読むALDS_1_C: Prime Numbers (続き)
さてじゃあどうしよう
奇数偶数だけで分けるんじゃなくて、６で割った余りで分類することにすると
3000万回ループが節約できるな
でもあんまりスマートな気はしない
やっぱり１億までのふるいってのが無理あるのでは
１億までの数の素数の判定だから、１万までの素数をふるいで求めて
順番に割るっていう作戦もあるか
これならふるいにかかる時間は無視できる
１万までの素数がいくつあるかわからないけど1000として
ひとつの数の判定をするのに最大1000回の割り算
たいていはもっと速く終わるだろうから100回くらいになるとすると
1万個判定しても100万回の割り算
それくらいならいけるでしょう
sieveは昨日のをそのまま使ってこんな感じ
def primes(max):
s = sieve(max)
p = [2]
for i in range(1, len(s)):
if s[i] == 0:
p.append(i * 2 + 1)
return p
def is_prime(n, p):
m = sqrt(n)
for q in p:
if q > m:
return True
if n % q == 0:
return False
return True
def main():
p = primes(10000)
n = int(input())
sum = 0
for _ in range(n):
x = int(input())
if is_prime(x, p):
sum += 1
print(sum)00.12s 5704KBでAC
よかったよかった
解説
sqrt(n)までで割ればn - 1まで割るよりずっと早い
あらかじめ素数を用意した方がいいことがあってふるいが有効
知ってた
サンプルコード
・・・
ふるってねえ
そのままsqrt(n)まで割ってる
def is_prime(n):
m = int(sqrt(n))
for q in range(2, m + 1):
if n % q == 0:
return False
return True00.36s 5680KBでAC、って
ふるいの絵はなんだったのか
まあ３倍速いしな！
エラトステネスのふるいの計算量はO(N log log N)なんだって
へー へー へー
DPL_3_B: Largest Rectangle
Largest Squareよりも思考・実装が星ひとつ以上増えてRectangle
自力でできそうな気がしませんね！
でも一度は自分で考える
