题面
要求$\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.ariels.xyz/archives/291.html
本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载,但请务必注明文章来源且不可用于商业目的。
One comment
太厉害啦!值得我们学习