ARC110
https://gyazo.com/530a2387f5888bc5beef773b2c723251
https://gyazo.com/ca2014b0f42b2b45f5267323ab8f2164
A
全部掛けて+1したら余りの条件を満たすけど、大きくなりすぎるので最小公倍数を求めました code:python
from math import gcd
N = int(input())
x = 1
for i in range(2, N + 1):
g = gcd(x, i)
x *= i // g
print(x + 1)
B
要するにこのオートマトンが受理するかどうか
https://gyazo.com/ddad8a5c2f2e6cbc723bf2ed788b5b2d
入力が1文字の時にトラップがあるのでそこだけ場合わけ
code:python
def solve(N, T):
if N == 1:
if T == "1":
return 2 * 10 ** 10
elif T == "0":
return 10 ** 10
for c in T:
for i in range(3):
nextStatei = statei - 1 and (c == "011"i) state = nextState
ret = 0
for i in range(3):
ret += (3 * 10 ** 10 - ((i - N) % 3 + N)) // 3 + 1
return ret