Submission #76264463

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long 

const int N=1e6+5,mod=998244353;

bool st;
int t,n,m;
int len[N];
__int128 s[N];
__int128 gcd(__int128 a,__int128 b) {
	return b==0?a:gcd(b,a%b);
}
bool ed;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cerr<<(double)(&st-&ed)/1024/1024<<'\n';
	cin>>t;
	len[0]=1;s[0]=1;
	for(int i=1;i<=19;i++) len[i]=len[i-1]*10%mod,s[i]=s[i-1]*10;
	while(t--) {
		cin>>n>>m;
		int nn=n,x=0;
		while(nn>0) x++,nn/=10;
		int res=0;
		for(int i=1;i<=x;i++) {
			int temp=len[i]-1;
			int num;
			if(i<x) num=(len[i]-len[i-1]+mod)%mod;
			else num=(n-len[i-1]+1+mod)%mod;
			if(temp==0) res+=n*num%mod;
			else res+=(n/(m/gcd(s[i]-1,m)))*num%mod;
			res%=mod;
		}cout<<res<<'\n';
	}
	return 0;
}

Submission Info

Judge Result