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が存在しません。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from fractions import gcd
from functools import reduce

def 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 cnt

N, 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日