ABC174
https://gyazo.com/4bdeee80ec6bac50babb6ec3cedc3c53
平方根は使いません
code:python
def main():
N, D = map(int, input().split())
count = 0
for _i in range(N):
X, Y = map(int, input().split())
if X * X + Y * Y <= D * D:
count += 1
print(count)
https://gyazo.com/3065cf7fe8d8bcf6873bc5e4c2ff0838
高々10^6なので順番に見ていけばいいだけなのだけど、到達しないケースがあるのが問題
訪問済みの剰余をマークして真面目にループ検出した
たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか
Twitterを見てると「なぜ剰余？」的な意見があったので少し補足
この数列は「前の数を10倍して7を足す」という操作を繰り返したもの
「Kの倍数」とは「Kで割ったあまりが0である数」
前の数の余りから次の数の余りがわかる
数列の各項を具体的に作らなくても、その余りだけわかればよい
大きな数を直接扱わなくてよい
余りが0になったらそれが探してた「Kの倍数」
余り0の数がみつかる前に、一度見た余りがまた出てきた場合、そこから先は同じことの繰り返しなので永遠に0に到達しない
余りはK通りしかないので、K回目までに結論が出る
code:python
def solve(K):
p = 7 % K
for i in range(K):
if p == 0:
return i + 1
return -1
p = (p * 10 + 7) % K
Q: 「K番目までにたどり着くことはわかっているので「たどり着かなかったらループだと判断」でもよかったか」
Yes、下記でACすることを確認した
code:python
def solve(K):
p = 7 % K
for i in range(K):
if p == 0:
return i + 1
p = (p * 10 + 7) % K
return -1
言及されてたことに気づいた
なるほど、そういう解き方、面白い。
https://gyazo.com/02c7ed56b882f0e212f9b53a84b60761
こういう筆算を考えた時、一の位ははてなが1個なので7に確定し、K X1の一の位が7になるX1も存在するなら一通りになる
X1が確定すると上1行が確定するので、次は2行目について「10の位ははてなが1個だから確定する」となる
このアルゴリズムが停止するのかどうかを考えてて気づいた
「余りの列はK番目までに0になるか、循環するかどちらか」の「循環する」に別の表現ができる
7がn個続いた数Aと、もっとたくさん続いた数BとでKでの余りが同じ場合、B-AはKの倍数
B-Aは、Bより小さな7が続く数に10^nを掛けた数なので「Bまでに余り0が見つかってない」という条件から、Kは10^nの約数
Kが1の時を除いてKの下一桁が偶数か5になる
このアルゴリズムでは「掛け算結果の下一桁が7にならない」ので速やかに停止してる
そこで停止しなかったものに関しては短いループに入らないことが保証されているので、K回目までに解にたどりつく