結果
問題 | No.1463 Hungry Kanten |
ユーザー |
![]() |
提出日時 | 2021-04-02 21:55:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 214 ms / 2,000 ms |
コード長 | 1,602 bytes |
コンパイル時間 | 848 ms |
コンパイル使用メモリ | 81,916 KB |
実行使用メモリ | 19,840 KB |
最終ジャッジ日時 | 2025-06-20 01:33:03 |
合計ジャッジ時間 | 2,314 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include <iostream> #include <vector> #include <set> using namespace std; typedef long long ll; typedef pair<ll, ll> P; const ll MOD0 = 109348985793; const ll MOD1 = 1092348904598; std::vector<int> enum_prime(int n){ // containing n std::vector<int> res; if (n <= 1) return res; std::vector<bool> p(n + 1); fill(p.begin() + 2, p.end(), true); for(int i = 2; i <= n; i++){ if(p[i]){ res.push_back(i); for(int j = i * 2; j <= n; j += i) p[j] = false; } } return res; } int main() { int n, k; cin >> n >> k; vector<int> prime = enum_prime(1000); int a[20]; vector<P> v[20]; for(int i = 0; i < n; i++){ cin >> a[i]; int b = a[i]; for(int p : prime){ if(b % p == 0){ int c = 0; while(b % p == 0){ c++; b /= p; } v[i].push_back(P(p, c)); } } } set<P> st; for(int b = 0; b < (1 << n); b++){ int e = 0; ll s0 = 1; ll s1 = 1; ll t = 0; for(int i = 0; i < n; i++){ if(!((b >> i) & 1)) continue; e++; for(P p : v[i]){ for(int j = 0; j < p.second; j++){ s0 = s0 * p.first % MOD0; s1 = s1 * p.first % MOD1; } } t += a[i]; } if(e >= k){ st.insert(P(s0, s1)); st.insert(P(t, t)); } } cout << (int)st.size() << endl; }