mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ SRM 数学 最小公倍数 問題 問題概要 lmc(1..M)=lcm(N+1,M)となる最小のMを求める. 解法 まず, 1,..,N,N+1,…,M N+1,…,M のlcmが一致することから,1…Nの中にlcmを作るのに寄与したものがいないので, 1…Nのなかに含まれる最大の素数の2倍の数がすくなくともMまでに含まれていなければならない. さらにM=2Nのとき, 1,..Nの数の倍数はすべて1,..Mの中に含まれるので, 必ず1,..Nがlcmに寄与しなくなるので, Mは最大でも2Nということになる. よってMの範囲は[(N以下で最大の素数), 2N]となる. あとは,Mをその範囲で動かしながらlcm(1..M)と… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2017%2F02%2F17%2F005756" title="SRM 661 div1 easy MissingLCM - srupのメモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-02-17 00:57:56 rich https://mmxsrup.hatenablog.com/entry/2017/02/17/005756 1.0 100%