結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
![]() |
提出日時 | 2023-05-27 11:54:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,400 ms / 3,000 ms |
コード長 | 3,113 bytes |
コンパイル時間 | 1,264 ms |
コンパイル使用メモリ | 118,924 KB |
最終ジャッジ日時 | 2025-02-13 09:04:44 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
//#pragma GCC target("avx2")//#pragma GCC optimize("O3")//#pragma GCC optimize("unroll-loops")#include <iostream>#include <iomanip>#include <algorithm>#include <vector>#include <string>#include <set>#include <map>#include <cassert>#include <cmath>#include <tuple>#include <queue>#include <bitset>#include <complex>#define _USE_MATH_DEFINES#include <math.h>using namespace std;using lg = long long;using pii = pair<int, int>;using pll = pair<lg, lg>;#define TEST clog << "TEST" << endl#define IINF 2147483647#define LLINF 9223372036854775807LL#define AMARI 998244353//#define AMARI 1000000007#define TEMOTO ((sizeof(long double) == 16) ? false : true)#define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000)#define el '\n'#define El '\n'long long ococo_gcd(long long a, long long b) {if (a < b) {long long kari = b;b = a;a = kari;}long long ans = a;while (a % b) {long long kari = b;b = a % b;a = kari;}return min(a, b);}lg lcm(lg a, lg b) {a /= ococo_gcd(a, b);return (a * b);}#define MULTI_TEST_CASE falsevoid solve(void) {lg n;cin >> n;lg nc = n;vector<lg> yakusuu;for (lg i = 1; i * i <= n; i++) {if (n % i == 0) {yakusuu.push_back(n / i);if (i * i != n)yakusuu.push_back(i);}}sort(yakusuu.begin(), yakusuu.end());int m = yakusuu.size();map<lg,int> soinsuu;for (lg i = 2; i * i <= n; i++) {while (n % i == 0) {soinsuu[i]++;n /= i;}}if (n != 1)soinsuu[n]++;vector<lg> dp(m, 0);dp[0] = 1;for (int i = 1; i < m; i++) {for (int j = 0; j < i; j++) {//yakusuu[j]→yakusuu[i]が何通りあるかif (yakusuu[i] % yakusuu[j] != 0)continue;lg temp = 1;for (map<lg, int>::iterator it = soinsuu.begin(); it != soinsuu.end(); it++) {//yakusuu[i]とyakusuu[j]がそれぞれit->firstで何回割れるか//毎回計算するとヤバいかもしれないので、TLEになったら前計算するlg ci = yakusuu[i], cj = yakusuu[j];int cnti = 0, cntj = 0;while (ci % it->first == 0) {ci /= it->first;cnti++;}while (cj % it->first == 0) {cj /= it->first;cntj++;}if (cnti == cntj)temp *= (cnti + 1);temp %= AMARI;}//clog << yakusuu[i] << ' ' << yakusuu[j] << ' ' << temp << el;dp[i] += temp * dp[j];dp[i] %= AMARI;}}//for (int i = 0; i < m; i++)clog << dp[i] << ' ';//clog << El;cout << dp[m - 1] << El;return;}void calc(void) {return;}int main(void) {cin.tie(nullptr);ios::sync_with_stdio(false);calc();int t = 1;if (MULTI_TEST_CASE)cin >> t;while (t--) {solve();}return 0;}