結果
問題 | No.2576 LCM Pattern |
ユーザー |
![]() |
提出日時 | 2023-12-18 23:32:25 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 925 bytes |
コンパイル時間 | 242 ms |
コンパイル使用メモリ | 31,360 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-27 08:31:11 |
合計ジャッジ時間 | 1,560 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <stdio.h>long long power_mod (long long a, long long b, long long mod_num) {long long ans = 1LL;if (b > 0LL) {ans = power_mod(a, b/2LL, mod_num);ans = (ans * ans) % mod_num;if (b%2LL == 1LL) {ans = (ans * (a % mod_num)) % mod_num;}}return ans;}int main () {long long n = 0LL;long long m = 0LL;int res = 0;long long ans = 1LL;long long mod_num = 998244353LL;long long p = 2LL;long long org_m = 0LL;res = scanf("%lld", &n);res = scanf("%lld", &m);org_m = m;while (p*p <= org_m) {long long cnt = 0LL;while (m%p == 0LL) {m /= p;cnt += 1LL;}ans *= power_mod(cnt+1LL, n, mod_num)+mod_num-power_mod(cnt, n, mod_num);ans %= mod_num;p += 1LL;}if (m > 1LL) {ans *= power_mod(2LL, n, mod_num)+mod_num-1LL;ans %= mod_num;}printf("%lld\n", ans);return 0;}