51Nod 1256-乘法逆元(扩展欧几里德)-白红宇

51Nod 1256-乘法逆元(扩展欧几里德)

阅读量：2029 次

发布时间：2019-04-28

本文共 873 字，大约阅读时间需要 2 分钟。

题目地址：

题意：给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

思路：K*M%N=1可以写成K*M-Y*N=1，这样公式就变成了扩展欧几里德求K值。因为是要求最小的，所以求出特解K以后，要变成(K%N+N)%N。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef __int64 LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;using namespace std;const int Maxn=1e6+10;bitset
               
                pri;LL gcd(LL a,LL b){ while(b!=0){ int r=b; b=a%b; a=r; } return a;}void exgcd(LL a,LL b,LL &x,LL &y){ if(b==0){ x=1; y=0; return ; } exgcd(b,a%b,x,y); LL t=x; x=y; y=t-(a/b)*y;}int main(){ LL m,n; LL x,y; while(~scanf("%lld %lld",&m,&n)){ LL G=gcd(m,n); m/=G; n/=G; exgcd(m,n,x,y); x=(x%n+n)%n; printf("%lld\n",x); } return 0;}

转载地址：http://mcsaf.baihongyu.com/

你可能感兴趣的文章