結果

問題 No.2318 Phys Bone Maker
コンテスト
ユーザー tnakao0123
提出日時 2023-06-23 18:41:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,199 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 57,572 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-06-30 22:24:56
合計ジャッジ時間 5,385 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2318.cc:  No.2318 Phys Bone Maker - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;

/* constant */

const int MOD = 998244353;

/* typedef */

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

/* global variables */

template <typename T>
T gcd(T m, T n) {  // m >= 0, n >= 0
  if (m < n) swap(m, n);
  while (n > 0) {
    T r = m % n;
    m = n;
    n = r;
  }
  return m;
}

template <typename T>
T lcm(T m, T n) {
  return m * (n / gcd<T>(m, n));
}

/* subroutines */

inline void addmod(int &a, int b) { a = (a + b) % MOD; }

/* main */

int main() {
  ll n;
  scanf("%lld", &n);

  vl ds;
  for (ll p = 1; p * p <= n; p++)
    if (n % p == 0) {
      ds.push_back(p);
      ll q = n / p;
      if (q != p) ds.push_back(q);
    }
  sort(ds.begin(), ds.end());
  int m = ds.size();
  //printf("m=%d\n", m);

  vi dp(m, 0);
  dp[0] = 1;

  for (int i = 0; i < m; i++)
    for (int j = 0; j < m; j++) {
      ll l = lcm(ds[i], ds[j]);
      if (l > ds[i]) {
	int k = lower_bound(ds.begin(), ds.end(), l) - ds.begin();
	addmod(dp[k], dp[i]);
      }
    }
  
  printf("%d\n", dp[m - 1]);

  return 0;
}
0