Atcoder 灰diff埋め ARC056~ARC113 振り返り
整数問題には苦手意識があるのでより多くの精進をしていきたいです.
ARC110 A - Redundant Redundancy【AC】
N<=30なので,愚直に全てのパターンを試しても間に合うように思えますが,N=30の時,答えは2329089562801=10^12近くあるので間に合いません.
N=3について考えると,2*3=6に1を足した7は2で割っても3で割っても1余ります.何故なら,6は2でも3でも割り切れるため,それに1を足せば余りは1になります.つまり,出力する解はN!=N*N-1*N-2*...*1でいいかと思われます.
しかし,例えば30!は265252859812191058636308480000000=10^32と,10^13という制約を守れません.そのため,Nまでの最小公倍数を求めれば良いです.最小公倍数はすべての数の倍数の中での最小の値であるので,N!の時と同じ効果が得られます.
pythonでの最小公倍数の求め方はこのサイトを参考にしました.
note.nkmk.me
from functools import reduce import math def my_lcm_base(x, y): return (x * y) // math.gcd(x, y) def my_lcm(*numbers): return reduce(my_lcm_base, numbers, 1) N = int(input()) print(my_lcm(*[i for i in range(2, N+1)])+1)