/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
2 以上の整数 N, D が与えられます。
N 以下の正整数であって D の倍数でないもののうち、正の約数の個数が最も多いものを求めてください。ただし、そのような正整数が複数存在する場合には、いずれか 1 つを出力してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10
- 2 \leq D \leq N \leq 10^{18}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
ここで、\text{case}_i は i 番目のテストケースであり、以下の形式で与えられる。
N D
出力
T 行出力せよ。i 行目には、i 番目のテストケースに対する答えを出力せよ。
入力例 1
4 10 2 17 4 2026 919 1000000000000 48
出力例 1
9 15 1680 843291048600
10 以下の正整数であって 2 の倍数でないものは 1, 3, 5, 7, 9 の 5 つであり、それぞれ正の約数の個数は 1, 2, 2, 2, 3 です。したがって、1 番目のテストケースでは 9 を出力します。
2 番目のテストケースでは、出力例の 15 のほか、6, 10, 14 のいずれかを出力しても正答となります。
Score : 575 points
Problem Statement
You are given integers N and D, each at least 2.
Among the positive integers at most N that are not multiples of D, find one with the maximum number of positive divisors. If there are multiple such positive integers, output any one of them.
You are given T test cases; solve each of them.
Constraints
- 1 \leq T \leq 10
- 2 \leq D \leq N \leq 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Here, \text{case}_i represents the i-th test case, and is given in the following format:
N D
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
4 10 2 17 4 2026 919 1000000000000 48
Sample Output 1
9 15 1680 843291048600
The positive integers at most 10 that are not multiples of 2 are the five integers 1, 3, 5, 7, 9, and the numbers of their positive divisors are 1, 2, 2, 2, 3, respectively. Therefore, output 9 for the first test case.
For the second test case, besides 15 in the sample output, outputting any of 6, 10, 14 is also accepted.