数字和与倍数

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file divsum.in Output file divsum.out

【题目描述】

若一个正整数的数字和被3整除,那么这个数也被3整除(反之亦然)。例如,3072被3整除,并且其数字和12也被3整除。这一性质对于模9也成立。

在这个问题中,我们将研究模其他正整数下的这个性质。

【输入格式】

第1行:一个正整数T(T<100),表示测试数据组数。
接下来的T行,每行包含3个正整数A,B,K。其中1<=A<=B<2^31且0<K<10000.

【输出格式】

对于每组测试数据,输出[A,B]内满足它和它的各位数字和同时被K整除的正整数个数。

【样例输入】

3
1 20 1
1 20 2
1 1000 4

【样例输出】

20
5
64

【提示】

对于20%的数据,1<=A,B<=20
对于100%的数据,1<=A,B<=2^31且0<K<10000,T<100

【来源】

UVa 11361 Investigating Div-Sum Property

刘汝佳,《算法竞赛入门经典训练指南》表2.2