結果
問題 |
No.528 10^9と10^9+7と回文
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:46:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 125 ms / 1,000 ms |
コード長 | 1,581 bytes |
コンパイル時間 | 144 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 67,732 KB |
最終ジャッジ日時 | 2025-03-20 18:47:38 |
合計ジャッジ時間 | 3,443 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
def mod_str(s, mod): res = 0 for c in s: res = (res * 10 + int(c)) % mod return res def main(): import sys N = sys.stdin.read().strip() mod1 = 10**9 mod2 = 10**9 + 7 m = len(N) sum_mod1 = 0 sum_mod2 = 0 # Precompute for k < m for k in range(1, m): pow_val = (k - 1) // 2 # Compute for mod1 term_mod1 = (9 * pow(10, pow_val, mod1)) % mod1 sum_mod1 = (sum_mod1 + term_mod1) % mod1 # Compute for mod2 term_mod2 = (9 * pow(10, pow_val, mod2)) % mod2 sum_mod2 = (sum_mod2 + term_mod2) % mod2 # Process m-digit numbers prefix_len = (m + 1) // 2 prefix_str = N[:prefix_len] start_str = '1' + '0' * (prefix_len - 1) if prefix_str >= start_str: # Generate palindrome candidate if m % 2 == 0: pali_candidate = prefix_str + prefix_str[::-1] else: pali_candidate = prefix_str + prefix_str[:-1][::-1] add = 1 if pali_candidate <= N else 0 # Compute for mod1 a_mod1 = mod_str(prefix_str, mod1) b_mod1 = mod_str(start_str, mod1) current_mod1 = (a_mod1 - b_mod1 + add) % mod1 sum_mod1 = (sum_mod1 + current_mod1) % mod1 # Compute for mod2 a_mod2 = mod_str(prefix_str, mod2) b_mod2 = mod_str(start_str, mod2) current_mod2 = (a_mod2 - b_mod2 + add) % mod2 sum_mod2 = (sum_mod2 + current_mod2) % mod2 print(sum_mod1) print(sum_mod2) if __name__ == '__main__': main()