結果
問題 | No.2151 3 on Torus-Lohkous |
ユーザー | chro_96 |
提出日時 | 2022-12-08 20:40:08 |
言語 | C (gcc 12.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,610 bytes |
コンパイル時間 | 367 ms |
コンパイル使用メモリ | 31,820 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 17:14:38 |
合計ジャッジ時間 | 1,162 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
ソースコード
#include <stdio.h> long long gcd (long long a, long long b) { if (b <= 0LL) { return a; } return gcd(b, a%b); } 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; } } return ans; } int main () { int t = 0; long long h = 0LL; long long w = 0LL; int res = 0; long long mod_num = 998244353LL; long long div[1000] = {}; res = scanf("%d", &t); while (t > 0) { long long ans = 0LL; long long d = 0LL; int div_cnt = 0; res = scanf("%lld", &h); res = scanf("%lld", &w); d = gcd(h, w); for (int i = 1; i*i <= ((int)d); i++) { if (((int)d)%i == 0) { div[div_cnt] = (long long)i; div_cnt++; if (((int)d)/i != i) { div[div_cnt] = d/((long long)i); div_cnt++; } } } for (int i = 0; i < div_cnt; i++) { if (div[i] == 4LL) { ans += 16LL; ans %= mod_num; } else if (div[i] >= 10LL && (div[i]-10LL)%6LL == 0LL) { long long tmp = power_mod((div[i]-4LL)/3LL, d/div[i]-1LL, mod_num); tmp *= (div[i]*div[i])%mod_num; tmp %= mod_num; ans += tmp; ans %= mod_num; } } ans += h*w; ans %= mod_num; if (d > 3LL) { ans += 2LL*d; ans %= mod_num; } if (d > 3LL && d%3LL == 0LL) { ans += 6LL*d; ans %= mod_num; } printf("%lld\n", ans); t--; } return 0; }