結果
| 問題 | No.941 商とあまり |
| ユーザー |
 yosupot
|
| 提出日時 | 2019-12-04 02:38:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,042 bytes |
| コンパイル時間 | 2,597 ms |
| コンパイル使用メモリ | 203,068 KB |
| 最終ジャッジ日時 | 2025-01-08 07:36:41 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 102 TLE * 2 |
ソースコード
# 1 "main.cpp"# 1 "<built-in>"# 1 "<command-line>"# 1 "main.cpp"# 1 "/Users/yosupo/Programs/Algorithm/expander/dummy_include/bits/stdc++.h" 1#include <bits/stdc++.h># 5 "main.cpp" 2using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }template <class T> using V = vector<T>;template <class T> using VV = V<V<T>>;# 1 "/Users/yosupo/Programs/Algorithm/src/util/fast_io.h" 1struct Scanner {FILE* fp = nullptr;char line[(1 << 15) + 1];size_t st = 0, ed = 0;void reread() {memmove(line, line + st, ed - st);ed -= st;st = 0;ed += fread(line + ed, 1, (1 << 15) - ed, fp);line[ed] = '\0';}bool succ() {while (true) {if (st == ed) {reread();if (st == ed) return false;}while (st != ed && isspace(line[st])) st++;if (st != ed) break;}if (ed - st <= 50) reread();return true;}template <class T, enable_if_t<is_same<T, string>::value, int> = 0>bool read_single(T& ref) {if (!succ()) return false;while (true) {succ();size_t sz = 1;while (st + sz < ed && !isspace(line[st + sz])) sz++;ref.append(line + st, sz);st += sz;if (st != ed) break;}return true;}template <class T, enable_if_t<is_integral<T>::value, int> = 0>bool read_single(T& ref) {if (!succ()) return false;bool neg = false;if (line[st] == '-') {neg = true;st++;}ref = T(0);while (isdigit(line[st])) {ref = 10 * ref + (line[st++] - '0');}if (neg) ref = -ref;return true;}template <class T> bool read_single(V<T>& ref) {for (auto& d : ref) {if (!read_single(d)) return false;}return true;}void read() {}template <class H, class... T> void read(H& h, T&... t) {bool f = read_single(h);assert(f);read(t...);}Scanner(FILE* _fp) : fp(_fp) {}};struct Printer {public:template <bool F = false> void write() {}template <bool F = false, class H, class... T>void write(const H& h, const T&... t) {if (F) write_single(' ');write_single(h);write<true>(t...);}template <class... T> void writeln(const T&... t) {write(t...);write_single('\n');}Printer(FILE* _fp) : fp(_fp) {}~Printer() { flush(); }private:static constexpr size_t SIZE = 1 << 15;FILE* fp;char line[SIZE], small[50];size_t pos = 0;void flush() {fwrite(line, 1, pos, fp);pos = 0;}void write_single(const char& val) {if (pos == SIZE) flush();line[pos++] = val;}template <class T, enable_if_t<is_same<T, string>::value, int> = 0>void write_single(const T& val) {for (char c : val) write_single(c);}template <class T, enable_if_t<is_integral<T>::value, int> = 0>void write_single(T val) {if (pos > (1 << 15) - 50) flush();if (val == 0) {write_single('0');return;}if (val < 0) {write_single('-');val = -val;}size_t len = 0;while (val) {small[len++] = char('0' + (val % 10));val /= 10;}reverse(small, small + len);memcpy(line + pos, small, len);pos += len;}template <class T> void write_single(const V<T>& val) {auto n = val.size();for (size_t i = 0; i < n; i++) {if (i) write_single(' ');write_single(val[i]);}}};# 15 "main.cpp" 2# 40 "main.cpp"template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {return os << "P(" << p.first << ", " << p.second << ")";}template <class T> ostream& operator<<(ostream& os, const V<T>& v) {os << "[";for (auto d : v) os << d << ", ";return os << "]";}# 1 "/Users/yosupo/Programs/Algorithm/src/bitop.h" 1int popcnt(uint x) { return __builtin_popcount(x); }int popcnt(ull x) { return __builtin_popcountll(x); }int bsr(uint x) { return 31 - __builtin_clz(x); }int bsr(ull x) { return 63 - __builtin_clzll(x); }int bsf(uint x) { return __builtin_ctz(x); }int bsf(ull x) { return __builtin_ctzll(x); }# 52 "main.cpp" 2ll gcd(ll a, ll b) {if (b == 0) return a;return gcd(b, a % b);}V<bool> solve(ll m, V<ll> v) {int n = int(v.size());V<bool> ans(m + 1);if (n == 1) {ans[v[0]] = true;return ans;}ll mi = 1, md = TEN(9);for (ll d : v) {md = min(md, d - 1);mi *= d;if (mi > m) break;}if (mi > m) {return ans;}if (md == 1) {for (ll i = mi; i <= m; i++) ans[i] = true;return ans;}if (n == 2) {for (ll d: v) {for (ll i = mi; i <= m; i += d - 1) ans[i] = true;}return ans;}# 98 "main.cpp"for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) continue;ll f0 = (v[i] - 1);ll f1 = v[i] * (v[j] - 1);for (int c = 0; c < f0; c++) {ll base = mi + f1 * c;if (base > m) break;for (ll x = base; x <= m; x += f0) {ans[x] = true;}}}# 128 "main.cpp"}if (n >= 4) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) continue;for (int k = 0; k < n; k++) {if (i == k || j == k) continue;ll w = mi / v[i] / v[j] / v[k];for (ll tm = 0; tm < 3; tm++) {ll z = v[k] * w + (v[k] - 1) * tm;ll f0 = (v[i] - 1);ll f1 = v[i] * (v[j] - 1);for (int c = 0; c < f0; c++) {ll base = z * v[i] * v[j] + f1 * c;if (base > m) break;for (ll x = base; x <= m; x += f0) {ans[x] = true;}}}}}}}return ans;}int main() {Scanner sc = Scanner(stdin);Printer pr = Printer(stdout);int n; ll x;sc.read(n, x);V<ll> a(n);sc.read(a);for (ll& d: a) d++;auto ans = solve(x + 1, a);for (int i = 2; i <= x + 1; i++) {auto f = ans[i];pr.write(f ? '1' : '0');}pr.writeln();return 0;}