题面

要求$\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 <iostream>
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<<i<<endl;
    }
    return 0;
}

版权属于：来自星星的薇薇安

本文链接：https://www.starroad.top/archives/291.html

如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！