結果

問題 No.2318 Phys Bone Maker
コンテスト
ユーザー Carpenters-Cat
提出日時 2023-05-30 14:21:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,613 ms / 3,000 ms
コード長 1,800 bytes
コンパイル時間 2,296 ms
コンパイル使用メモリ 210,476 KB
最終ジャッジ日時 2025-02-13 16:31:54
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
unordered_map<ll, ll> mp, mp_cn;
unordered_map<ll, vector<ll>> ss_cnt;
std::vector<ll> sosu;
ll m = 998244353;
ll cnt_yk(ll a){
	if (mp_cn.find(a) != mp_cn.end()) {
		return mp_cn[a];
	}
	if (a == 1) {
		return mp_cn[a] = 1;
	}
	mp_cn[a] = 0;
	for (ll i = 1; i * i <= a; i ++) {
		if (a % i == 0) {
			mp_cn[a] ++;
			if (i * i < a) {
				mp_cn[a] ++;
			}
		}
	}
	return mp_cn[a];
}
ll calc(ll a) {
	if (mp.find(a) != mp.end()) {
		return mp[a];
	}
	mp[a] = 0;
	for (ll i = 1; i * i <= a; i ++) {
		if (a % i == 0) {
			ll kj = calc(i);
			for (int j = 0; j < sosu.size(); j ++) {
				if (ss_cnt[i][j] == ss_cnt[a][j]) {
					kj *= (ss_cnt[a][j] + 1);
					kj %= m;
				}
			}
			mp[a] += kj;
			if (i * i < a && i > 1) {
				ll b = a / i;
				ll kj = calc(b);
				for (int j = 0; j < sosu.size(); j ++) {
					if (ss_cnt[b][j] == ss_cnt[a][j]) {
						kj *= (ss_cnt[a][j] + 1);
						kj %= m;
					}
				}
				mp[a] += kj;
			}
			mp[a] %= m;
		}
	}
	return mp[a];
}
int main() {
	ll N;
	cin >> N;
	mp[1] = 1;
	ll n = N;
	for (ll i = 2; i * i <= N; i ++) {
		if (n < i) break;
		if (n % i == 0) {
			sosu.push_back(i);
			while (n % i == 0) {
				n /= i;
			}
		}
	}
	if (n > 1) {
		sosu.push_back(n);
	}
	for (ll i = 1; i * i <= N; i ++) {
		if (N % i == 0) {
			ss_cnt[i] = sosu;
			ll j = i;
			for (int p = 0; p < sosu.size(); p ++) {
				ss_cnt[i][p] = 0;
				ll q = sosu[p];
				while (j % q == 0) {
					ss_cnt[i][p] ++;
					j /= q;
				}
			}
			if (i * i < N) {
				ll a = N / i;
				ss_cnt[a] = sosu;
				ll j = a;
				for (int p = 0; p < sosu.size(); p ++) {
					ss_cnt[a][p] = 0;
					ll q = sosu[p];
					while (j % q == 0) {
						ss_cnt[a][p] ++;
						j /= q;
					}
				}
			}
		}
	}
	cout << calc(N) << endl;
}
0