結果
問題 | No.2576 LCM Pattern |
ユーザー |
|
提出日時 | 2024-01-08 17:08:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,151 bytes |
コンパイル時間 | 886 ms |
コンパイル使用メモリ | 84,968 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-27 19:37:19 |
合計ジャッジ時間 | 1,779 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <iostream>#include <vector>#include <map>#include <cmath>const int mod = 998244353;// 素因数分解函数std::map<int, int> prime_factorize(int n) {std::map<int, int> prime_factors;while (n % 2 == 0) {prime_factors[2]++;n /= 2;}int f = 3;while (f * f <= n) {if (n % f == 0) {prime_factors[f]++;n /= f;} else {f += 2;}}if (n != 1) {prime_factors[n]++;}return prime_factors;}// 快速幂函数,用于计算 a^b % modlong long modpow(long long base, int exp, int modulus) {base %= modulus;long long result = 1;while (exp > 0) {if (exp & 1) result = (result * base) % modulus;base = (base * base) % modulus;exp >>= 1;}return result;}int main() {int N, M;std::cin >> N >> M;auto CP = prime_factorize(M);long long ans = 1;for (auto const& kvp : CP) {int v = kvp.second;ans = ans * (modpow(v + 1, N, mod) - modpow(v, N, mod) + mod) % mod;}std::cout << ans << std::endl;return 0;}