구 역 원 [수론]

이틀 동안 아무것도 만 들 지 못 했 어 요.. /. TT
역 원 을 처음 접 한 것 은 11 년 대련 의 마지막 문제 다. 멘 붕 아, 할 줄 몰라.. 아무것도 할 줄 몰라.
예 를 들 면: (8/2)%5  우 리 는 a * b * c * d * e * f * g...........................................................................그리고 계속.（3*8）%5=4=4%5
===
(a / b)% Mod 를 계산 할 때 b% Mod 의 역 원 p (b 가 역 원 이 있 는 조건 은 gcd (b, Mod) = 1 이 고 분명히 소 수 는 역 원 이 있 을 것 이다) 를 계산 한 다음 에 (a * p)% Mod 에서 결과 c 를 얻는다.여기 b 의 역 원 p 만족 (b * p)% Mod = 1.먼저 간단하게 증명 하 겠 습 니 다: (a / b)% Mod = c;   (b*p)%Mod=1;    ==》   (a/b)*(b*p) %Mod=c;    ==》    (a*p)%Mod=c;
위 에서 결론 의 정확성 을 알 수 있다. 물론 여기 b 는 a 의 인자 가 필요 하 다.다음은 b 와 Mod 에 따라 우리 가 역 원 p 를 어떻게 계산 하 는 지 알 아야 한다.유클리드 알고리즘 을 확장 하 는 것 은 모두 가 알 고 있 을 것 이다. 바로 a, b 를 알 고 한 조 의 해 (x, y) 를 구하 여 a * x + b * y = 1 을 만 드 는 것 이다.여기 서 구 하 는 x 는 바로 a% b 의 역 원 이 고 y 는 b% a 의 역 원 이다.ExtGcd (b, Mod, x, y) 를 호출 합 니 다. x 는 b% Mod 의 역 원 p 입 니 다. b% Mod 의 역 원 p 를 구 하 는 또 다른 방법 이 있 습 니 다. 즉, p = b ^ (Mod - 2)% Mod 입 니 다. b ^ (Mod - 1)% Mod = 1 (여기 에는 Mod 가 소수 이기 때 문 입 니 다).
이상:http://hi.baidu.com/zhanggmcn/item/ef4dadceb4fb993e449416e7
예 를 들다   3/2%5=4; 2*3%5=1  ==>  (3/2)*(2*8)%5=4  ==> (3*8)%5=4
===
유클리드 확장: 우선 유클리드 확장 은 선형 방정식 과 관련 된 문 제 를 푸 는 데 사용 되 기 때문에 우 리 는 선형 방정식 부터 분석 합 니 다. 지금 이 선형 방정식 을 a * x + b * y = m 라 고 가정 합 니 다. 만약 이 선형 방정식 이 풀 리 면 반드시 gcd (a, b) | m, 즉 a, b 의 최대 공약 수 는 m (m% gcd (a, b) = 0) 를 제거 할 수 있 습 니 다. 증명 은 간단 합 니 다. a% gcd 때문에(a, b) = = b% gcd (a, b) = 0 이기 때문에 a * x + b * y 는 반드시 gcd (a, b) 를 제거 할 수 있 고 선형 방정식 이 성립 되면 a * x + b * y 를 m 로 대체 하여 위의 결론 을 얻 을 수 있 으 며 위의 결론 을 이용 하여 선형 방정식 의 해 가 있 는 지 판단 할 수 있다.      그러면 a * x + b * y = m 라 는 선형 방정식 이 성립 된 상황 에서 어떻게 x 와 y 를 풀 수 있 습 니까?      a 1 = a = a / gcd (a, b), b1 = b / gcd (a, b), m1 = m / gcd (a, gcd (a, b). a * x1 + b * y1 = gcd (a, b) 이 방정식 의 x1 과 y1 을 충족 시 키 는 것 을 우리 가 먼저 구 할 수 있다 면 x = x1* m1, y = y1 * m1, y = y1 * m1 을 구 할 수 있다. 유클리드 알고리즘 gcd (a, b) = gcd (a, b) = gcd (b, b) = gcd (b, a, a% b) = gcd (b, a% b, a% b, a% b), 그래서 a * x 1 + b * x 1 + b * y1 = gcd (a, b, b, b) = gc2 + (a% b)* y2, 이제 변형 만 하면 확장 유클리드 알고리즘 에 사용 되 는 식 을 얻 을 수 있 습 니 다.* y2. 이 두 가지 식 이 있 으 면 우 리 는 유클리드 로 최대 공약수 를 구 할 때 해당 하 는 매개 변수 x, y 의 변 화 를 알 수 있 습 니 다. 이제 다시 돌 이 켜 보면 유클리드 알고리즘 을 확장 하 는 코드 를 잘 이해 할 수 있 습 니 다. 실제로 유클리드 를 확장 하 는 것 은 a 와 b 의 최대 공약수 를 구 하 는 동시에 방정식 a * x1 + b * y1 = gcd (a, b) 도 만족 시 킬 것 입 니 다.다음 코드 에서 두 드 러 진 부분 은 표준 유클리드 알고리즘 의 코드 입 니 다.

__int64 exGcd(__int64 a,__int64 b,__int64 &x,__int64 &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    __int64 g=exGcd(b,a%b,x,y);
    __int64 temp=x;
    x=y;
    y=temp-(a/b)*y;
    return g;
}

     2. 그러면 x, y 의 한 조 해 는 x1 * m1, y1 * m1 이지 만 방정식 을 만족 시 키 기 위해 무한 여러 개 를 풀 기 때문에 실제 문제 에서 일반적으로 x 또는 y 의 최소 정수 값 을 구 합 니 다. x 를 예 로 들 면 어떻게 풀 어야 합 니까? 아니면 방정식 에 착안 하여 현재 의 x, y 는 a * x + b * y = m 를 가득 채 웠 습 니 다. 그러면 a * (x + n * b) + b * (y - n * a) = m 도 분명히 성립 되 었 습 니 다. x + n * b 를 얻 을 수 있 습 니 다.(n =..., - 2, - 1, 0, 1, 2,...) 는 방정식 의 모든 x 해 의 집합 입 니 다. 모든 x 는 y 와 대응 하 는 것 이 분명 하기 때문에 x 를 풀 때 y 의 수 치 를 고려 하지 않 아 도 됩 니 다. k 를 취하 면 x + k * b > 0, x 의 최소 정수 치 는 (x + k * b)% b 여야 합 니 다. 그런데 이 수 치 는 정말 가장 작은 것 입 니까? 만약 우리 가 방정식 의 가장 양쪽 을 동시에 gcd (a, b) 로 나 누 면방정식 이 a1 * x + b1 * y = m1 로 변 하면 위의 분석 과 같이 이때 의 최소 값 은 (x + k * b1)% b1 이 어야 한다. b1 < = b 이기 때문에 이 값 은 반드시 이전의 값 보다 작 을 것 이다. 실제 구 해 과정 에서 일반적으로 while (x < 0) x + = b1 로 정확 한 조건 을 만족 시 켜 야 한다. 순환 을 빨리 끝내기 위해 b1 을 b (b 는 b1 의 배수) 로 바 꿀 수 있다., 그리고 b 를 배 수 를 곱 한 후에 x 에 추가 합 니 다.
이상http://cie.xtu.edu.cn/acmfan_cn/viewthread.php?tid=844
===

           :
#include<iostream>
#define __int64 long long
using namespace std;
//   3x+4y=1 ax+by=1
//     x0=-1，y0=1    x=-1+4k,y=1-3k
inline __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y)//ax+by=1  a,b gcd，                 
{
    __int64 ans,t;
    if(b==0){x=1;y=0;return a;}
    ans=extend_gcd(b,a%b,x,y);t=x;x=y;y=t-(a/b)*y;
    return ans;
    }
//(a/b)%mod=c    p，(p*b)%mod=1
//(a/b)*(p*b)%mod=c*1%mod=c
// (p*b)%mod=1     p*b-(p*b)/mod*mod=1    p，b       ax+by=1
//  x=p（x    ）,y=p/mod,a=b,b=b*mod     extend_gcd(b,b*mod,x,y)   (a/b)%mod      a*p%mod
int main()
{
    __int64 a,b,x,y,c,gcd,mod,p;//ax+by=c
    while(cin>>a>>b>>c)
    {
          gcd=extend_gcd(a,b,x,y);
          cout<<x<<"  "<<y<<endl;
          if(c%gcd){cout<<"  !"<<endl;continue;}
          cout<<"x="<<x*c/gcd<<" y="<<y*c/gcd<<endl;
          }
    return 0;
    }

다음으로 이동:http://hi.baidu.com/foreverlin1204/item/5e3da7d437b4d290270ae76c
===
대련 I 문제 와 대신 코드 에 따라 템 플 릿 을 하나 더 고 쳤 습 니 다.
템 플 릿 붙 이기:

#include <iostream>
using namespace std;
int x,y,rev;

void extend_Euclid(int a, int b)
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return;
    }
    extend_Euclid(b, a%b);
    int t = x;
    x = y;
    y = t - a/b*y;
}


int main()
{
    //b%mod   
    int b,mod;
    while(cin>>b>>mod){
       // x=0;y=0;
        extend_Euclid(b,mod);
        cout<<(x%mod+mod)%mod<<endl;
    }
    return 0;
}