提出 #69338184

---

ソースコード 拡げる

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#include <cassert>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

int n, m, Y;
int a[20];
int f[1 << 20];
int g[1 << 20];

signed main() {
	int i, j;

	cin >> n >> m >> Y;
	rep(i, n) cin >> a[i];
	
	rep(i, (1 << n)) {
		int l = 1;
		rep(j, n) {
			if ((i >> j) % 2) {
				int g = gcd(l, a[j]);
				if (l / g > Y / a[j]) {
					l = Y + 1;
					break;
				}
				l = lcm(l, a[j]);
			}
		}
		f[i] = Y / l;
	}

	rep(i, (1 << n)) g[i] = f[i];
	rep(i, n) {
		rep(j, (1 << n)) {
			if ((j >> i) % 2 == 0) {
				g[j] -= g[j + (1 << i)];
			}
		}
	}

	int ans = 0;
	rep(i, (1 << n)) {
		int bcnt = 0;
		rep(j, n) if ((i >> j) % 2) bcnt++;
		if (bcnt == m) ans += g[i];
	}
	cout << ans << endl;
	return 0;
}

提出情報

ジャッジ結果