nyoj1110 一个简单数学题

―个简单的数学题

描述

挖掘机技术哪家强，那么问题就来了？？

现在有这样一个问题,（A/B) ≡ C%P(P素数,A ≡ 0%B)

已知 B，P, n ≡ A % P;

输入

输入T组数据
输入三个数n，B，P（n,B,P在int范围内）

输出

输出 C

样例输入

1
3 4 5

样例输出

2

提示

“≡” 即为同余
比如：6 ≡ 0%2 , 7 ≡ 2%5 , 5 ≡ 5%7

上传者

ACM_张书军

思路：A/B = C % P;（P是素数）

这个题要用到乘法逆元即B * B（-1） = 1 % P;
B(-1) 可以以用费马小定理（B ^（P-1）= 1 % p）求出 即B（-1）= B^(P-2);
A/B 分子分母同时乘以B（-1） 即 A*B（-1）/ (B * B(-1)) = A * B^(P-2)
已知A % P = n ，所以 A * B^(p-2) = n * B^(p-2) % P (B^(p-2)用快速幂解决)//学长给的思路 比较详细
我的推理过程：

A*B(-1)%p=c%p

n%p=A%p

n*B(-1)%p=A*B(-1)%p=c%p

B * B（-1） = 1 % P

#include
      
       
#include
       
         #include
        
          #include
         
           using namespace std; long long n,b,p; long long pow_mod(int num) { long long res =1; while(num) { if(num&1) res=res*b%p; b=b*b%p; num>>=1; } return res; } int main() { int t; cin>>t; while(t--) { scanf("%lld%lld%lld",&n,&b,&p); long long res=pow_mod(p-2); printf("%lld\n",(res*n)%p); } } 
         
        
       
      

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];