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
