Quiz

https://atcoder.jp/contests/abc150/tasks/abc150_d

AC code

https://atcoder.jp/contests/abc150/submissions/11677574

間違った解法

A[i]をそれぞれ2で割る
それらでlcmを求める
lcmでMを割ったおよそ半分が答え

lcm求めるだけではダメなサンプル

4 282984448
16384 32768 278528 557056

答え
0

なぜならば、(2k+1)は奇数しか取れないから。
a = 2 x a' として、

f:id:peroon:20200409021100p:plain

code

ll two_num(ll v){
  ll cnt=0;
  while(v%2==0){
    cnt++;
    v/=2;
  }
  return cnt;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M;
    cin>>N>>M;

    VI A(N);
    rep(i, N) cin >> A[i];

    // それぞれの2で割れる回数が一致しないと不可能
    // (2k+1)は奇数にしかなれないため
    set<ll> se;
    for(ll a : A){
      ll b = two_num(a);
      se.insert(b);
    }
    if(se.size()!=1){
      p(0);
      return 0;
    }

    rep(i,N){
      A[i]/=2;
    }

    ll a = A[0];
    FOR(i,1,N){
      a = lcm(a, A[i]);
    }

    ll num = M/a;
    ll ans = (num+1)/2;
    p(ans);
    
    return 0;
}