結果
問題 | No.2578 Jewelry Store |
ユーザー |
|
提出日時 | 2023-01-13 17:57:22 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,469 bytes |
コンパイル時間 | 3,256 ms |
コンパイル使用メモリ | 119,596 KB |
最終ジャッジ日時 | 2025-02-10 01:58:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 TLE * 32 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>#include <atcoder/modint>using mint = atcoder::modint998244353;mint solve_naive(uint32_t n, uint64_t m, std::vector<uint64_t> a, std::vector<uint32_t> w) {{std::vector<uint64_t> a2;std::vector<uint32_t> w2;for (uint32_t i = 0; i < n; ++i) if (m % a[i] == 0) {a2.push_back(a[i]);w2.push_back(w[i]);}a.swap(a2);w.swap(w2);n = a.size();}mint ans = 0;for (uint32_t s = 1; s < uint32_t(1) << std::min(n, 30u); ++s) {mint prod = 1;uint64_t l = 1;for (uint32_t i = 0; i < n; ++i) if ((s >> i) & 1) {l = std::lcm(l, a[i]);prod *= w[i];}if (l == m) {ans += prod;}}return ans;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);uint32_t t;uint64_t m;std::cin >> t >> m;for (uint32_t testcase = 0; testcase < t; ++testcase) {uint32_t n;std::cin >> n;uint32_t x0, c, d;std::cin >> x0 >> c >> d;std::vector<uint32_t> w(n);w[0] = x0;for (uint32_t i = 1; i < n; ++i) {w[i] = (c * mint(w[i - 1]) + d).val();}std::vector<uint64_t> a(n);for (auto &e : a) std::cin >> e;std::cout << solve_naive(n, m, a, w).val() << '\n';}return 0;}