2020-05-06 競プロ初中級者100問 ABC150D Semi Common Multiple はじめにカテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。 全問題の一覧はこちらです 問題https://atcoder.jp/contests/abc150/tasks/abc150_d 方針基本的には解説PDFの通りです。 a_k / 2を考え、それらの最小公倍数を奇数倍したものの数を数えれば良いです。 ただし、a_kのそれぞれが2で割れる回数が全て等しくない場合、条件を満たすXが存在しません。 コード1234567891011121314151617181920212223242526from fractions import gcdfrom functools import reducedef lcm(a,b): # lcmは標準ライブラリには存在しない return a * b // gcd(a,b)def ls_lcm(A): # リストを引数に取れる return reduce(lcm ,A)def ls_gcd(A): # リストを引数に取れる return reduce (gcd, A)def count_two(n): # 2で割れる回数を取得 cnt = 0 while(n & 1 == 0): # 最下位ビットが0かどうか cnt += 1 n = n >> 1 # 右ビットシフト return cntN, M = map(int, input().split())A = list(map(int, input().split()))if len(set([count_two(a) for a in A])) != 1: print (0) exit()A = [a//2 for a in A] # a_k/2 を考えるlc = ls_lcm(A)print ((M + lc) // (2*lc)) # 最小公倍数を奇数倍したものが条件を満たす 記事情報 投稿日:2020年5月6日 最終更新日:2020年5月8日 次の記事 JOI2007本戦C 最古の遺跡 前の記事 ABC075C Bridge