NOSQ - No Squares Numbers
题意翻译
【题意】不能被任何($\neq 1$ 的)平方数整除的数叫做“无平方数”。如:$13,15,210$ 是“无平方数”,$25,108,18$ 不是“无平方数”。特别地,$1$ 也是“无平方数”。
现在的问题是:请你输出$a$ 和$b$ 之间所有包含数字$d$ 的无平方数的个数。如:$10$ 和$40$ 之间所有包含数字$3$ 的无平方数有:$13, 23, 30, 31, 33, 34, 35, 37, 38, 39$ 。
【输入】第一行一个整数$T$ ($1\leq T \leq 20000$ ),表示数据组数。后面有$T$ 行,每行三个整数$a,b,d$ ,意义如上
($1\leq a,b \leq 100000,0 \leq d \leq 9$ )
Translated by @RobertGusMocoratioen
题目描述
A square free number is defined as a number which is not divisible by any square number.
For example, 13, 15, 210 are square free numbers, where as 25 (divisible by 5\*5), 108 (divisible by 6\*6), 18 (divisible by 3\*3) are not square free numbers. However number 1 is not considered to be a square and is a squarefree number.
Now you must find how many numbers from number a to b, are square free and also have a digit d inside it.
For example for in the range 10 to 40 te squarefree numbers having digit 3 are 13, 23, 30, 31, 33, 34, 35, 37, 38, 39
输入输出格式
输入格式
The first line contains an integer T, which is the number of test-cases
Then follow T lines, each containing 3 integers a, b and d.
1 <= T <= 20,000
1 <= a <= b <= 100,000
0 <= d <= 9
输出格式
Print one integer which is the required number as described in the problem statement.
输入输出样例
输入样例 #1
3
10 40 3
1 100 4
1 100000 7
输出样例 #1
10
9
26318