結果
問題 |
No.941 商とあまり
|
ユーザー |
![]() |
提出日時 | 2019-12-04 07:16:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,004 bytes |
コンパイル時間 | 2,447 ms |
コンパイル使用メモリ | 204,580 KB |
最終ジャッジ日時 | 2025-01-08 07:43:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 100 WA * 4 |
ソースコード
#include<bits/stdc++.h> using namespace std; using P = pair<int, int>; const int M = 1000000007; int x; vector<bool> ans; void output() { for (bool i : ans) { cout << i; } cout << '\n'; } int gcd(int a, int b) { while (b > 0) { int t = a % b; a = b; b = t; } return a; } void dfs(const vector<int>& v, int j, int s, int g) { if (j + 1 == v.size()) { for (int i = 0; s + i < x; i += v[j]) { ans[s + i] = true; } return; } int ng = gcd(g, v[j + 1]); for (int i = 0; s + i < x; i += v[j]) { if (i > 0 && i % v[j + 1] == 0) break; ans[s + i] = true; if (g == 0 || ng < g) { dfs(v, j + 1, s + i, ng); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n >> x; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a.begin(), a.end()); long long sum = 1; for (int i = 0; i < n; ++i) { sum *= a[i] + 1; if (sum > M) break; } ans = vector<bool>(x); if (sum - 1 > x) { output(); return 0; } int bs = sum - 1; if (n == 1) { ans[a[0] - 1] = true; output(); return 0; } for (int i = 0; i < n; ++i) { for (int j = 0; bs + j <= x; j += a[i]) { ans[bs + j - 1] = true; } } if (a[0] > 1) { vector<int> b; for (int i = 0; i < n; ++i) { if (i == 0 || a[i - 1] < a[i]) { b.push_back(a[i]); } } int sz = b.size() < a.size() ? b.size() : b.size() - 1; do { vector<int> v(sz); int ss = 1; for (int i = 0; i < sz; ++i) { v[i] = ss * b[i]; ss *= b[i] + 1; } dfs(v, 0, bs - 1, 0); } while (next_permutation(b.begin(), b.end())); } output(); return 0; }