Loading... ## 题面 要求$\cfrac{a}{b}\%9973$,但由于$a$很大,我们只给出$n=A\%9973$,保证$a$必能被$b$整除,且$gcd(b,9973)=1$。 <!--more--> ## 解法 设$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$即可。 ## 代码 ```cpp #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; } ```<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/291.html">https://www.starroad.top/archives/291.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:June 29th, 2019 at 04:04 pm © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat