結果

問題 No.2318 Phys Bone Maker
コンテスト
ユーザー sepa38
提出日時 2023-05-26 22:25:27
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 716 bytes
コンパイル時間 10,614 ms
コンパイル使用メモリ 288,340 KB
最終ジャッジ日時 2025-02-13 07:19:36
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 42 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int main() {
  long int n;
  long int mod = 998244353;
  cin >> n;
  vector<long int> v;
  long int t = 1;
  while (t * t <= n) {
    if (n % t == 0) {
      v.push_back(t);
      if (t != n / t) v.push_back(n/t);
    }
    t++;
  }
  unordered_map<long int, long int> dp;
  for (auto& val : v) {
    dp.insert(make_pair(val, 0));
  }
  sort(v.begin(), v.end());
  dp[1] = 1;
  for (auto& val1 : v) {
    for (auto& val2 : v) {
      long int l = lcm(val1, val2);
      if (l == val1) continue;
      dp[l] += dp[val1];
      dp[l] %= mod;
    }
  }
  cout << dp[n] << endl;
}
0