题面
要求$\cfrac{a}{b}\%9973$,但由于$a$很大,我们只给出$n=A\%9973$,保证$a$必能被$b$整除,且$gcd(b,9973)=1$。
解法
设$a=9973k_1+n$,$\cfrac{a}{b}=c$,$c=9973k_2+ans$,题目所求为$ans$。
则$$a=bc=b \times (9973k_2+ans)$$
$$a=9973k_1+n$$
代入整理得$$9973(k_1-k_2)=b \times ans-n$$
$\because ans \in N_+$,且$ans \in [0,9973)$。
直接依次枚举$ans$即可。
代码
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int i,b,n;
cin>>n>>b;
for(i=0;i<9973;i++){
if((((b%9973)*i)%9973-n)%9973==0){
break;
}
}
cout<
此处评论已关闭