結果

問題 No.2578 Jewelry Store
コンテスト
ユーザー fdironia
提出日時 2023-12-06 07:33:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,499 ms / 3,500 ms
コード長 5,533 bytes
コンパイル時間 1,688 ms
コンパイル使用メモリ 116,444 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-27 01:05:13
合計ジャッジ時間 14,851 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <numeric>

using namespace std;

using ll = long long;
using pli = pair<ll, int>;
using mli = map<ll, int>;
using vp = vector<pli>;

constexpr int Z = 998244353;

// copyed Pollard-rho part from cp-algorithms
//ll mult(ll a, ll b, ll mod) {
//    return (__int128)a * b % mod;
//}
//
//ll f(ll x, ll c, ll mod) {
//    return (mult(x, x, mod) + c) % mod;
//}
//
//ll rho(ll n, ll x0=2, ll c=1) {
//    ll x = x0;
//    ll y = x0;
//    ll g = 1;
//    while (g == 1) {
//        x = f(x, c, n);
//        y = f(y, c, n);
//        y = f(y, c, n);
//        g = gcd(abs(x - y), n);
//    }
//    return g;
//}
//
//ll bexp(ll a, ll n, ll m) {
//    if (n == 0) {
//        return 1;
//    }
//    if (n % 2 == 1) {
//        return mult(a, bexp(a, n - 1, m), m);
//    }
//    ll t = bexp(a, n / 2, m);
//    return mult(t, t, m);
//}
//
//bool mr(ll p) {
//    if (p < 2) return 0;
//    if (p == 2) return 1;
//    if (p == 3) return 1;
//    ll d = p - 1, r = 0;
//    cerr << p << endl;
//    while (!(d & 1)) ++r, d >>= 1;
//    for (ll k = 0; k < 10; ++k) {
//        ll a = rand() % (p - 2) + 2;
//        ll x = bexp(a, d, p);
//        if (x == 1 || x == p - 1) continue;
//        for (int i = 0; i < r - 1; ++i) {
//            x = mult(x, x, p);
//            if (x == p - 1) break;
//        }
//        if (x != p - 1) return 0;
//    }
//    cerr << "YES" << endl;
//    return 1;
//}
//
//void pr(ll a, mli &fmap, int exp=1) {
//    if (a == 1) {
//        return;
//    }
//    if (mr(a)) {
//        fmap[a] += exp;
//        return;
//    }
//
//    ll f = -1;
//    for (int i = 1; i <= 10; i++) {
//        f = rho(a, 0, i);
//        if (f < a) {
//            break;
//        }
//    }
//
//    if (f == -1) {
//        cerr << "NO" << endl;
//    }
//
//    int e2 = 0;
//    while (a % f == 0) {
//        a /= f;
//        e2++;
//    }
//
//    pr(a, fmap, exp);
//    pr(f, fmap, exp * e2);
//}


ll quick_pow(ll x, ll p, ll mod) {
  ll ans = 1;
  while (p) {
    if (p & 1) ans = (__int128)ans * x % mod;
    x = (__int128)x * x % mod;
    p >>= 1;
  }
  return ans;
}

bool Miller_Rabin(ll p) {
  if (p < 2) return 0;
  if (p == 2) return 1;
  if (p == 3) return 1;
  ll d = p - 1, r = 0;
  while (!(d & 1)) ++r, d >>= 1;
  for (ll k = 0; k < 10; ++k) {
    ll a = rand() % (p - 2) + 2;
    ll x = quick_pow(a, d, p);
    if (x == 1 || x == p - 1) continue;
    for (int i = 0; i < r - 1; ++i) {
      x = (__int128)x * x % p;
      if (x == p - 1) break;
    }
    if (x != p - 1) return 0;
  }
  return 1;
}

ll f(ll x, ll c, ll n) { return ((__int128)x * x + c) % n; }

ll Pollard_Rho(ll x) {
  ll s = 0, t = 0;
  ll c = (ll)rand() % (x - 1) + 1;
  int step = 0, goal = 1;
  ll val = 1;
  for (goal = 1;; goal <<= 1, s = t, val = 1) {
    for (step = 1; step <= goal; ++step) {
      t = f(t, c, x);
      val = (__int128)val * abs(t - s) % x;
      if ((step % 127) == 0) {
        ll d = gcd(val, x);
        if (d > 1) return d;
      }
    }
    ll d = gcd(val, x);
    if (d > 1) return d;
  }
}

void fac(ll x, mli &fmap, int exp) {
  if (x < 2) return;
  if (Miller_Rabin(x)) {
    fmap[x] += exp;
    return;
  }
  ll p = x;
  while (p >= x) p = Pollard_Rho(x);
  int e = 0;
  while ((x % p) == 0) x /= p, e++;
  fac(x, fmap, exp), fac(p, fmap, exp * e);
}

int main() {
    int tc;
    ll m;
    cin >> tc >> m;

//    cerr << rho(4) << endl;

    bool mone = m == 1;

    mli facs_map;
    fac(m, facs_map, 1);
    vp facs(facs_map.begin(), facs_map.end());

//    vp facs;
//    for (int i = 2; 1ll * i * i <= m; i++) {
//        if (m % i == 0) {
//            int p = 0;
//            while (m % i == 0) {
//                m /= i;
//                p++;
//            }
//
//            facs.emplace_back(i, p);
//        }
//    }
//    if (m > 1) {
//        facs.emplace_back(m, 1);
//    }
    int fc = facs.size();

    for (int i = 0; i < fc; i++) {
        cerr << facs[i].first << " " << facs[i].second << endl;
    }

    while (tc--) {
        int n, b, c, d;
        cin >> n >> b >> c >> d;
        int w[1<<fc], cw = b;
        fill(w, w + (1 << fc), 1);
        for (int i = 0; i < n; i++) {
            ll a;
            cin >> a;

            int cur = 0;
            for (int j = 0; j < fc; j++) {
                auto [f, p] = facs[j];

                int cp = 0;
                while (a % f == 0) {
                    a /= f;
                    cp++;
                }

                if (cp == p) {
                    cur ^= 1 << j;
                } else if (cp > p) {
                    cur = -1;
                    break;
                }
            }

            if (cur >= 0 && a == 1) {
                w[cur] = 1ll * w[cur] * (cw + 1) % Z;
            }

            cw = (1ll * c * cw + d) % Z;
        }

        int dp[1<<fc];
        copy(w, w + (1 << fc), dp);
        for (int j = 0; j < fc; j++) {
            for (int i = 0; i < (1 << fc); i++) {
                if (i >> j & 1) {
                    dp[i] = 1ll * dp[i] * dp[i^(1<<j)] % Z;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < (1 << fc); i++) {
            int pc = 0;
            for (int j = 0; j < fc; j++) {
                pc += i >> j & 1;
            }

            ans = (0ll + ans + dp[i] * ((fc - pc) % 2 == 0 ? 1 : -1) + Z) % Z;
        }

        cout << (mone ? (ans + Z - 1) % Z : ans) << endl;
    }

    return 0;
}
0