Noi模拟 数字 打表找规律 奇妙推论

数字(num)

【题目描述】

小D喜欢的数有这样的性质:令n为正整数,S(n)为n的各位数字之和,令,若一个数能表示成x*d(x)这种形式,则这个数是小D喜欢的。

小D想知道在区间[L,R]中,有多少个数是他喜欢的。

有多组数据。

【输入数据】

第一行一个整数T,表示数据组数。

以下每一行两个数L、R(保证区间合法),代表询问[L,R]。

【输出数据】

输出T行,每行一个数,表示在这个区间内小D喜欢的数出现了多少次。

【样例输入】

3

1 5

3 9

8 8

【样例输出】

2

2

0

【数据范围】

对于30%的数据,L,R<=10^6;

对于100%的数据,T<=20,L,R<=10^18。

////////////////////////////////////////////////////////////////////////////////////////

我们先打个表可以发现,d函数是富有规律的,是1->9的循环
d(X) = (X – 1) % 9 + 1
比如d(1) = 1,d(81) = 9等

这样子我们考虑怎么快速判断一个数X是否为小D喜欢的数。
我们发现d函数的值域为[1,9],我们考虑枚举d(x)函数的值为k。
那么x的值呢。我们之前推出 d(X) = (X – 1) % 9 + 1
那么 (x – 1) % 9 + 1 = k
(x – 1) % 9 = k – 1
因为k – 1 < 9
所以 x % 9 = k
所以 x = k + 9 * T
那么 原式为(k + 9T) * k = X,当这个式子成立时,X为喜欢的数。
我们考虑两边 % 9K (因为k<=9)
k * k % 9k = X % 9k
我们接着考虑设LCM = 1 * 2 * 3 …… * 9
我们可以发现LCM是判断的循环节,也就是说x若喜欢,则x+LCM也必定喜欢。
这样子我们预处理除LCM以内的部分,然后维护前缀和O(1)询问即可。

发表评论