我想到了一个数位DP的解法，然而由于多组数据过于毒瘤，TLE了（

尝试把memset优化掉，虽然答案仍然正确但是还是TLE on #4

求大佬康康（可以帮忙卡常啊或者研究一下数位DP在此题的正确性）

另外求个时间复杂度（

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=205;
ll l,r,a,b,T,f[20][N][N][2],dig[20],cnt=0,t;
ll dfs(ll pos,ll moda,ll modb,ll lim){
	ll ans=0;
	if(f[pos][moda][modb][1]!=-1&&!lim&&f[pos][moda][modb][2]==t) return f[pos][moda][modb][1];
	if(!pos) return ((moda%b)!=(modb%a))?1:0;
	ll up=lim?dig[pos]:9;
	for(register int i=0;i<=up;i++){
		ans+=dfs(pos-1,(moda*10%a+i%a)%a,(modb*10%b+i%b)%b,lim&&(i==up));
	}
	if(!lim) f[pos][moda][modb][1]=ans,f[pos][moda][modb][2]=t;
	return ans;
}
ll solve(ll x){
	ll ans=0,k=x;
	cnt=0;
	while(x!=0) dig[++cnt]=x%10,x/=10;
	return dfs(cnt,0,0,1);
}
ll read(){
	char ch=getchar();
	ll w=0;
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch<='9'&&ch>='0') w=(w<<1)+(w<<3)+ch-'0',ch=getchar();
	return w;
}
void print(ll x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
int main(){
	ll TTT;
	TTT=read();
	while(TTT--){
		t++;
		a=read(),b=read(),T=read();
		while(T--){
			l=read(),r=read();
			print(solve(r)-solve(l-1)),putchar(' ');
		}
		puts("");
	}
}