Python3で解く AtCoder Beginner Contest 150 D - Semi Common Multiple

半公倍数って初めて聞いた。 まぁ定義に従って計算する。
ぱっと見、複数の値に対する最小公倍数を使うんだろうな。

結果的に、最小公倍数を計算しきってから大きさの判定をしていたせいで、一部REが発生していて、そこが原因と気付かず、ひたすら原因究明のためにsubしまくって、ようやく正解。

この順番じゃないとダメな理由は、よくわからなかったけど、多分オーバーフローとかそういうことでしょう。

概要

問題

• 偶数個の数列を与えられる。
• その数列の任意のにおいて、
  を満たすが存在する時、を半公倍数とする。
• 半公倍数の数は？

---

解くときに考えた内容

1. まず複数の最小公倍数（の最小公倍数をとする）を求める。

   • 最小公倍数をとった値に逐次的に最小公倍数をとっていけばいい。
   • つまり、があるとして、とすればいい。

2. 最小公倍数の半分の値（とする）が以下かどうか
   これはとなるようなpが存在するかということで、最も小さい条件を満たすものは最小公倍数の半分の値であり、それが条件を満たさない（つまり選んだ全てのにおいての形にならなずに、整数になってしまうものが存在する）場合は、半公倍数は存在しない。
3. あとはが負ではないということになっているので、 までのを考えればいい。 これは、上で最小公倍数の半分の値で成立すれば、あとはそれに最小公倍数を足していけば必ず成立する（必ずに整数が足されていくため）。最小公倍数以外を足したら任意ので成立しないからである。

   

   最小公倍数の半分の値で成立したら、その後最小公倍数を足していくと成立するイメージ

4. として取り得る最大をとする。
5. が答え

---

コード

lcm計算中にとの大きさの判定をする方法

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b

n, m = map(int, input().split())
A = set([int(x) for x in input().split()])
a_lcm = 1
for a in A:
    a_lcm = lcm(a_lcm, a)
    # mがlcmの半分よりも小さかったら0
    if (a_lcm / 2) > m:
        print(0)
        exit()
for a in A:
    if a_lcm / 2 % a == 0:
        print(0)
        exit()
# # あとは定数倍の数調べて終わり
ans = int((m - (a_lcm / 2)) // a_lcm) + 1
print(ans)

lcm計算後にとの大きさの判定をする方法(これはREが出る)

これで死ぬほどハマった。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b

n, m = map(int, input().split())
A = set([int(x) for x in input().split()])
a_lcm = 1
for a in A:
    a_lcm = lcm(a_lcm, a)
# mがlcmの半分よりも小さかったら0
if (a_lcm / 2) > m:
    print(0)
    exit()
for a in A:
    if a_lcm / 2 % a == 0:
        print(0)
        exit()
# # あとは定数倍の数調べて終わり
ans = int((m - (a_lcm / 2)) // a_lcm) + 1
print(ans)

---