Submission #76272378

---

Source Code Expand

import math

def f(n, m):
    MOD = 998244353
    ans = 0
    
    max_d = 0
    temp = n
    while temp > 0:
        max_d += 1
        temp //= 10
        
    p10 = 1
    pow10_mod_m = 1
    
    for _ in range(max_d):
        min_y = p10
        max_y = min(p10 * 10 - 1, n)
        
        count_y = max_y - min_y + 1
        if count_y <= 0:
            break
            
        pow10_mod_m = (pow10_mod_m * 10) % m
        d = (pow10_mod_m - 1 + m) % m
        
        g = math.gcd(m, d)
        k = m // g
        
        count_x = n // k
        
        term = ((count_x % MOD) * (count_y % MOD)) % MOD
        ans = (ans + term) % MOD
        
        p10 *= 10
        
    return ans

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    print(f(n, m))

Submission Info

Judge Result