题面

要求$\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;
}
Last modification:June 29, 2019
如果您觉得我的文章有用,给颗糖糖吧~