#936779 (C++17) No.2578 Jewelry Store

提出ソース
結果

問題	No.2578 Jewelry Store
コンテスト
ユーザー	pockyny
提出日時	2023-12-06 03:40:26
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,438 ms / 3,500 ms
コード長	5,818 bytes
コンパイル時間	3,349 ms
コンパイル使用メモリ	215,808 KB
最終ジャッジ日時	2025-02-18 08:18:07
ジャッジサーバーID （参考情報）	judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 54
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
using uint = uint32_t;
using ull = uint64_t;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

template <class F>
struct ycr {
	F f;
	template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args> decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F> decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

/**
 * Author: Hanfei Chen
 * Date: 2023-11-30
 * Description: Very fast factorization.
 * Source: https://judge.yosupo.jp/submission/110118
 * Status: Tested with https://judge.yosupo.jp/problem/factorize
 */
struct montgomery {
	using T = ull; /// start-hash
	using u128 = __uint128_t;
	T n, n2, r, t, e;
	montgomery(T n_) : n(n_) {
		assert(n < (T(1) << 62));
		assert(n % 2 == 1);
		n2 = n * 2;
		r = n & 3;
		for (int z = 0; z < 5; z++) r *= 2-n*r;
		r = -r;
		assert(r * n == T(-1));
		t = -T(n) % n;
		e = T(-u128(n) % n);
	} /// end-hash

	T reduce(u128 a) const { /// start-hash
		return T((a + u128(T(a) * r) * n) >> 64);
	}
	T mult(T a, T b) const {
		return reduce(u128(a) * b);
	} /// end-hash

	T encode(T a) const { /// start-hash
		return mult(a, e);
	}
	T decode(T a) const {
		a = reduce(a);
		return a < n ? a : a-n;
	} /// end-hash

	T pow(T a, ll b) const { /// start-hash
		assert(b >= 0);
		T v = t;
		while (b) {
			if (b & 1) v = mult(v, a);
			a = mult(a, a);
			b >>= 1;
		}
		return v;
	} /// end-hash

	bool is_prime() const {
		assert(n >= 3);
		assert(n & 1);

		T d = n-1; /// start-hash
		int s = __builtin_ctzll(d);
		d >>= s;
		auto check = [&](T a) -> int {
			a %= n;
			if (a == 0) return 1;
			T p = pow(encode(a), d);
			if (decode(p) == 1 || decode(p) == n-1) return 0;
			for (int z = 0; z < s; z++) {
				p = mult(p, p);
				if (decode(p) == n-1) return 0;
			}
			return -1;
		}; /// end-hash

		for (T a : {2,325,9375,28178,450775,9780504,1795265022}) { /// start-hash
			int w = check(a);
			if (w) return w == 1;
		}
		return true; /// end-hash
	}

	ull pollard() const {
		assert(n >= 3);
		assert(n & 1);

		if (is_prime()) return n; /// start-hash
		while (true) {
			T c = mt() % (n-1) + 1;
			T y = mt() % (n-1) + 1;
			auto f = [&](T a) -> T {
				return reduce(u128(a) * a + c);
			};
			for (T s = 1; ; s *= 2) {
				T x = n2-y;
				int m = int(min(T(1) << (__lg(n)/6), s));
				for (int i = 0; i < int(s/m); i++) {
					T w = t, z = y;
					for (int j = 0; j < m; j++) {
						y = f(y);
						w = mult(w, y+x);
					}
					T g = __gcd(decode(w), n);
					if (g != 1) {
						if (g < n) return g;
						for (int j = 0; j < m; j++) {
							z = f(z);
							if ((g = __gcd(decode(z+x), n)) != 1) {
								if (g < n) return g;
								goto fail;
							}
						}
						assert(false);
					}
				}
			}
fail:;
		} /// end-hash
	}

	// facs = {prime factors of (n-1)}
	bool is_root(T g, const vc<T>& facs) { /// start-hash
		assert(g >= 2);
		g = encode(g);
		for (auto f : facs) {
			if (decode(pow(g, (n-1) / f)) == 1) return false;
		}
		return true;
	} /// end-hash
};

bool is_prime(ull n) { /// start-hash
	if (n <= 1) return false;
	if (n == 2) return true;
	if (n % 2 == 0) return false;
	return montgomery(n).is_prime();
} /// end-hash

ull get_divisor(ull n) { /// start-hash
	assert(n > 1);
	if (n % 2 == 0) return 2;
	return montgomery(n).pollard();
} /// end-hash

vc<ull> factorize(ull n) { /// start-hash
	vc<ull> res;
	yc([&](auto self, ull v) -> void {
		if (v == 1) return;
		ull d = get_divisor(v);
		if (d == v) {
			res.push_back(d);
			return;
		}
		self(d);
		self(v/d);
	})(n);
	return res;
} /// end-hash

#include <atcoder/modint>

using namespace atcoder;
using mint = modint998244353;
mint dp[1<<15];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);
	int T; ll m;
	cin >> T >> m;
    ll x = m;
    auto res = factorize(x);
    map<ll,ll> mp;
    for(auto x:res) mp[x]++;
    vector<pair<ll,ll>> di;
    for(auto p:mp) di.push_back({p.first,p.second});
    while(T){
        T--;
        ll i,j,n,b,c,d;
        cin >> n >> b >> c >> d;
        vector<ll> a(n);
        vector<mint> w(n);
        for(i=0;i<n;i++) cin >> a[i];
        w[0] = b;
        for(i=1;i<n;i++) w[i] = (c*w[i - 1] + d);
        for(i=0;i<(1<<di.size());i++) dp[i] = 1;
        for(i=0;i<n;i++){
            if(m%a[i]==0 && w[i].val()){
                ll x = 0;
                int j = 0;
                for(auto p:di){
                    ll cnt = 0;
                    while(a[i]%p.first==0){
                        a[i] /= p.first; cnt++;
                    }
                    if(cnt<p.second) x |= 1<<j;
                    j++; 
                }
                (dp[x] *= (1 + w[i]));
            }
        }
        //cout << dp[0] << " " << dp[1] << " " << dp[2] << " " << dp[3] << endl;
        for(j=0;j<di.size();j++){
            for(i=0;i<(1<<di.size());i++){
                if(!(i>>j&1)) (dp[i] *= dp[i^(1<<j)]);
            }
        }
        mint ans = 0;
        for(i=0;i<(1<<di.size());i++){
            int c = 0;
            for(j=0;j<di.size();j++){
                if(i>>j&1) c = 1 - c;
            }
            if(!c) (ans += dp[i]);
            else (ans -= dp[i]);
        }
        if(m==1) ans--;
        cout << ans.val() << "\n";
    }
	// while (T--) {
	// 	ull n;
	// 	cin >> n;
	// 	auto res = factorize(n);
	// 	sort(res.begin(), res.end());
	// 	cout << res.size();
	// 	for (auto p : res) {
	// 		cout << ' ' << p;
	// 	}
	// 	cout << '\n';
	// }

	// return 0;
}
yukicoder

結果

ソースコード
