Submission #76254322

Source Code Expand

from math import gcd

MOD = 998244353
for _ in range(int(input())):
    N, M = map(int, input().split())
    ans = 0
    for k in range(19):
        t = 10 ** (k + 1) - 1
        if t <= N:
            p = 9 * 10**k
        elif 10**k <= N:
            p = N - 10**k + 1
        else:
            p = 0
        g = gcd(10 ** (k + 1) - 1, M)
        # print(f"{k=} {g=} {p=}")
        ans += N // (M // g) * p
        ans %= MOD
    print(ans)

Submission Info

Submission Time
Task E - x + y ≡ x + y
User shogo314
Language Python (PyPy 3.11-v7.3.20)
Score 450
Code Size 462 Byte
Status AC
Exec Time 155 ms
Memory 108876 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 1
AC × 7
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 49 ms 79920 KiB
01_random_00.txt AC 141 ms 108628 KiB
01_random_01.txt AC 143 ms 108640 KiB
01_random_02.txt AC 153 ms 108756 KiB
01_random_03.txt AC 148 ms 108860 KiB
01_random_04.txt AC 155 ms 108628 KiB
01_random_05.txt AC 148 ms 108876 KiB