시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 256 MB | 143 | 47 | 35 | 29.661% |
주머니 안에 A개의 공이 있고, 그중에 정확히 B개의 빨간색 공이 있다. (A ≥ B ≥ 1, A ≠ 1)
공놀이를 하려 주머니에서 공을 꺼내던 현이는 우연히도 무작위로 두 개의 공을 뽑았을 때 적어도 하나는 빨간색이 아닐 확률이 자연수 N에 대해 정확히 1/N2이 됨을 알고 신기해했다.
현이는 주어진 N에 대해 이 조건을 만족하는 자연수의 쌍 (A, B)이 무한히 많음을 곧 깨달았고, 그중 A가 M번째로 작은 쌍은 무엇인지 궁금해졌다.
현이는 공놀이를 자주 해서 궁금증 또한 자주 생길 것이다. 당신은 궁금증을 해소해 주기 위해 현이가 공놀이를 Q번 하는 동안 모두 답을 해주어야 한다!
첫 번째 줄에 공놀이를 하는 횟수 Q가 주어진다.
두 번째 줄부터 Q+1번째 줄까지 각 줄마다 자연수 N, M이 공백으로 구분되어 주어진다.
Q개의 줄에 각 줄마다 조건을 만족하는 자연수의 쌍 (A, B)중 A가 M번째로 작은 쌍을 공백으로 구분하여 출력한다. 수가 매우 커질 수 있으니 109+7로 나눈 나머지를 출력한다.
1 2 1
8 7
2 3 1 1 4
18 17 5 1