| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.18 초 | 1024 MB | 44 | 14 | 10 | 28.571% |
Mariya has come up with the following definition for a rich number. It is given a positive integer $X$. Then a positive integer $N$ is called a rich number (relative to $X$) if the sum of its divisors except $N$ is greater than $X$. For example, the number 10ドル$ (whose sum of divisors is 1ドル+2+5 = 8$) is rich relative to $X=7$ but it isn’t rich relative to $X=12$.
Write a program rich_num to help Mariya. The program will be given queries that are ordered triples of positive integers $(L, R, V)$ and for each query it should calculate the number of rich numbers relative to $V,ドル which are greater than or equal to $L$ and less than or equal to $R$.
The first line of the standard input contains one positive integer $Q$ – the number of queries that your program has to process.
Each of the next $Q$ lines contains three positive integers $L,ドル $R$ and $V,ドル which describe a query for your program to process.
Your program should output to the standard output $Q$ lines – one line for each query in the order of the input. Each line should contain the answer to the corresponding query.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $Q \le 10^3,ドル $R \le 10^3,ドル $V \le 10^5$ |
| 2 | 10 | $Q \le 10^5,ドル $R \le 10^4,ドル $V = 10$ |
| 3 | 30 | $Q \le 10^5,ドル $R \le 10^5,ドル $V \le 10$ |
| 4 | 55 | $Q \le 10^5,ドル $R \le 10^5,ドル $V \le 10^5$ |
3 5 15 5 1 20 20 12 20 10
6 2 4