Problem Statement
For positive integers aa and bb, define concat(a,b)concat(a,b) as the integer formed by writing aa and bb one after another. More formally, concat(a,b)concat(a,b) is defined as follows.
- Let AA and BB be the strings formed by writing aa and bb in decimal, respectively. Let CC be the string formed by concatenating AA and BB in this order. The value of CC interpreted as an integer in decimal notation is concat(a,b)concat(a,b).
For example, if a=123a=123 and b=45b=45, then concat(a,b)=12345concat(a,b)=12345.
You are given positive integers NN and MM.
Find the number, modulo 998244353998244353, of pairs (x,y)(x,y) of positive integers not greater than NN such that concat(x,y)≡x+y(modM)concat(x,y)≡x+y(modM).
You are given TT test cases; solve each one.
Constraints
- 1≤T≤1041≤T≤104
- 1≤N≤10181≤N≤1018
- 2≤M≤1092≤M≤109
- All input values are integers.
Input
The input is given from Standard Input in the following format, where caseicasei denotes the ii-th test case:
TT
case1case1
case2case2
⋮⋮
caseTcaseT
Each test case is given in the following format:
NN MM
Output
Output TT lines. The ii-th line should contain the answer for the ii-th test case.
For each test case, output the number, modulo 998244353998244353, of pairs (x,y)(x,y) satisfying the condition.
Sample 1
| Input复制 | Output复制 |
|---|---|
4 3 2 123 456 20260530 460 123456789123456789 998244353 |
3 0 922576091 422081792 |
For the first test case, three pairs (x,y)(x,y) satisfy the condition: (2,1),(2,2),(2,3)(2,1),(2,2),(2,3).
算法分析
我们让N的位数是len，循环从1到len，len的最大值就是20。所以concat(a,b)=10^i*a+b模m和a+b模m相同。所以999……99（9的个数是i）的最大公约数和N同余，想到这一点代码就很好写出出来了。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
long long T,n,m;
int main(){scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&m);__int128 tm = m;__int128 sum = 0;__int128 x = 1;__int128 y = 0;for(int i = 1; i<=20; i++){sum = (sum+n/(m/__gcd(tm,10*x-1))*max(y,min(n-x+1,9*x)))%mod;//一个小小的压行^_^x*=10;}printf("%lld\n",(long long)sum%mod);//__int128官方是没有配输出的，所以要转long long。}return 0;
}