Submission #69372166

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

// 実質無限大
constexpr long long INF = 2000000000000000000;

// 最小公倍数を求める（ただし大きすぎたらINFを返す）関数
long long my_lcm (long long a, long long b) {
  if (a==INF||b==INF) return INF;
  long long g = gcd(a,b);
  if (1.0*a/g*b>INF) return INF;
  return a/g*b;
}

// 組み合わせ計算（nが小さいので簡易版）
long long nCr (int n, int r) {
  long long tmp = 1;
  for (int i=0; i<r; i++) {
    tmp *= (n-i);
    tmp /= (i+1);
  }
  return tmp;
}

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, m;
  long long y;
  cin >> n >> m >> y;

  vector<long long> a(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  long long result = 0;

  //////////////////// 処理 ////////////////////

  // 発生するセミの種類をビット管理して全パターンループ
  for (int i=0; i<(1<<n); i++) {

    // 最小公倍数計算用
    long long tmp = 1;

    // そうなる回数
    long long num = 0;

    // 何種類のセミが発生するか
    int count = 0;

    // セミの種類ごとに最小公倍数と種類数を更新
    for (int j=0; j<n; j++) {
      if (i&(1<<j)) {
        count++;
        tmp = my_lcm(tmp,a.at(j));
      }
    }

    // そうなる年数を求める
    num = y/tmp;

    // 包除原理っぽい感じでがんばる
    // 発生するセミの種類数がm未満なら無視
    // m以上で、mと偶奇が一致するならComb[種類数,m]倍したものを足す
    // m以上で、mと偶奇が異なるならComb[種類数,m]倍したものをを引く
    // 途中でlong longをはみ出す場合があるが、最終的に0以上y以下に戻ってくるのでよし
    if (count>=m) {
      if ((count+m)%2==0) {
        result += num*nCr(count,m);
      } else {
        result -= num*nCr(count,m);
      }
    }
    

  }

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result