Description

• T组询问。

Data Constraint

Solution

• 先说一个结论：$D(n)=(n-1)\ mod\ 9+1$D(n)=(n−1) mod 9+1。证明如下：
• 首先，快速判断一个大数n是否为9的倍数有一个黑科技：那就是将其每个位数相加，判断得到的和是否为9的倍数。（即判断S(n)是否为9的倍数。）因为我们可以看一看9的倍数：0,9,18,27,36……可以发现，如果不进位，则个位+9；如果进位，则十位+1，个位-1；以此类推。
• 然后，可以推得$n\equiv S(n)\ (mod\ 9)$n≡S(n) (mod 9)。因此，每次从$n\to S(n)$n→S(n)模9的余数是不变的。

• 若数$n=k×D(k)$n=k×D(k)是小D喜欢的数，则$n+22680=(k+\frac{22680}{D(k)})×D(k)$n+22680=(k+D(k)22680​)×D(k)也是小D喜欢的数。
• 原因很简单。$22680=2^3·3^4·5·7$22680=23⋅34⋅5⋅7，因此，当$1≤x≤9$1≤x≤9时，$\frac{22680}x$x22680​均为整数。
• 那么，我们可以预处理出22680以内的答案，打个前/后缀和，即可对每个问题$O(1)$O(1)解决。

• 时间复杂度：$O(22680+T)$O(22680+T)。

Code

#include <bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;

const ll X=22680;
int i,d[X+1],x,T;
ll c[X+1],L,R,l,r;

inline ll que(ll x) {return x/X*c[X]+c[x%X];}

int main()
{
	fo(i,1,X) 
	{
		d[i]=i/10000%10+i/1000%10+i/100%10+i/10%10+i%10;
		while(d[i]>9) d[i]=d[d[i]];
		fo(x,1,9) if(i%x==0&&d[i/x]==x) {c[i]=1;break;}
		c[i]+=c[i-1];
	}
	for(scanf("%d",&T);T--;)
	{
		scanf("%lld%lld",&L,&R);
		printf("%lld\n",que(R)-que(L-1));	
	}
}