結果

問題 No.2798 Multiple Chain
コンテスト
ユーザー lingfunny
提出日時 2024-06-28 22:52:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 1,947 bytes
コンパイル時間 2,684 ms
コンパイル使用メモリ 253,748 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 22:52:39
合計ジャッジ時間 3,974 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using LLL = __int128;

const int primes[] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 20, 31, 37};

inline LL qpow(LL x, LL k, LL mod) {
	LL res = 1;
	while(k) {
		if(k&1) res = (LLL)res*x%mod;
		x = (LLL)x*x%mod;
		k >>= 1;
	}
	return res;
}

inline bool millerRabin(LL x) {
	if(x < 2 || !(x&1)) return x==2;
	LL d = x-1; int t = 0;
	while(!(d&1)) d>>=1, ++t;
	for(int i=1, j;i<=12;++i) {
		if(x == primes[i]) return true;
		if(x%primes[i] == 0 || qpow(primes[i], x-1, x) != 1) return false;
		LL u = qpow(primes[i]%x, d, x);
		if(u == 1) continue;
		for(j=0;j<t;++j) {
			if(u == x-1) break;
			u = (LLL)u*u%x;
		}
		if(j >= t) return false;
	}
	return true;
}

inline LL gcd(LL x, LL y) {
	if(x < y) swap(x, y);
	while(y) {
		x %= y;
		swap(x, y);
	}
	return x;
}
inline LL f(LL x, LL c, LL mod) { return ((LLL)x*x+c)%mod; }
std::mt19937_64 rrand(114514);
inline LL pollardRho(LL x) {
	LL s = 0, t = 0, val, c = rrand()%(x-1)+1;
	for(int goal = 1; ; goal <<= 1, s = t) {
		val = 1;
		for(int step = 1; step <= goal; ++step) {
			t = f(t, c, x);
			val = (LLL)val * abs(t-s) % x;
			if(!(step%127)) {
				LL d = gcd(val, x);
				if(d > 1) return d;
			}
		}
		LL d = gcd(val, x);
		if(d > 1) return d;
	}
}
map <LL, int> M;
void fac(LL n) {
	if(millerRabin(n) || n <= 2) {
		if (n > 1) M[n] += 1;
		return;
	}
	LL x = n;
	while(x == n) x = pollardRho(n); 
	fac(x), fac(n / x);
}

LL n, ans, dp[80][80];
int tot;

int main() {
	cin >> n;
	fac(n);
	for (auto [_, c] : M) tot = max(tot, c);
	// dp[i][j]: len = i, \sum = j
	dp[0][0] = 1;
	for (int x = 0; x <= 64; ++x)
		for (int i = 1; i <= 64; ++i)
			for (int j = x; j <= 64; ++j) dp[i][j] += dp[i - 1][j - x];
	auto calc = [&](int L) {
		LL res = 1;
		for (auto [_, c] : M) {
			res *= dp[L][c];
		}
		return res;
	};
	for (int L = 1; L <= tot; ++L) ans += calc(L) - calc(L - 1);
	printf("%lld\n", ans);
	return 0;
}

// pollard_rho
0