BZPRO

#4703. 幸运数

内存限制：256 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

你应该知道，什么是最大公约数：对于任意两个非零整数x，y，若整数d能同时被x和y整除，则称d为x与y的公约数
。定义x与y的最大公约数gcd(x, y)为x与y的最大的公约数。如gcd(6, 9) = 3，gcd(12, 16) = 4，gcd(25, 32) =
 1，等等。这里，我们定义什么是幸运数：对于一个正整数d，我们使用di表示d在十进制表示下，按从低位到高位
顺序的第i位数字。设F(d)表示d的奇数位的数字之和，即F(d) = d1 + d3 + d5 + ……；设G(d)表示d的偶数位的
数字之和，即G(d) = d2 + d4 + d6 + ……；若F(d)与G(d)均大于0，且F(d)与G(d)的最大公约数不超过K，则称d
为幸运数。其中K是一个已知的常数。举个例子来说，若d = 641，则d1 = 1，d2 = 4，d3 = 6，F(641) = 1 + 6 =
 7，G(641) = 4。此时F(d)与G(d)的最大公约数即gcd(7, 4)等于1。则当K不小于1时641是幸运数。请你回答下面
的问题：对于给定的K，在不小于L并且不超过R的所有整数中，有多少个数是幸运数？注意，输入文件包含多组测
试数据。

输入格式

第一行包含一个整数T，表示有T组测试数据。
接下来T行，每行包含三个整数K、L、R，表示一次询问。

输出格式

输出T行，每行一个整数，依次表示每组测试数据的答案。
1 ≤ L ≤ R ≤ 10^18， 1 ≤ K ≤ 10^2，1 ≤ T ≤ 1000

样例

样例输入


			
5

1 1 10

2 28 34

100 987654321 987654321

1 1 50000

1 50001 100000

样例输出


			
0

5

1

30298

30309

【样例解释】

K = 1时，1到10之间不存在幸运数。

K = 2时，28到34之间的幸运数有28、29、31、32、34，共5个。

K = 100时，987654321是幸运数。

K = 1时，1到50000之间的幸运数有30298个，50001到100000之间的幸运数有30309个。

数据范围与提示

BZPRO Powered by Remmina.
Github Repository