#1690. [语言月赛 202410] 寻找质数

[语言月赛 202410] 寻找质数

题目描述

称一个数 xx 是孤独数,当且仅当 xx 是质数且 xx 除以 mm 的余数是 rr。

给出正整数 n,m,r,k n,m,r,k,求 1∼n1\sim n 内第 kk 大的孤独数。若不存在输出 −1-1。

例如,3,5,11,73,5,11,7 这四个数中,从大到小排序时 77 是第 22 名,那么我们说 77 是第二大的。

输入格式

输入一行四个正整数 n,m,r,kn,m,r,k,含义见题目描述。

输出格式

输出一行一个整数表示 1∼n1\sim n 内第 kk 大的孤独数,若不存在则输出 −1-1。

样例

20 3 2 2
11
10000 6 4 1
-1
97 10 7 6
7

题目来源:洛谷 B4046