곱셈 역 원 의 몇 가지 구법 총화

곱셈 역 원
축 계 중의 요소 에 대해 모든 수 a 는 이에 대응 하 는 유일한 곱셈 역 원 x 를 가지 고 있 기 때문에 x. 1 (mod n)  하나의 수 에 역 원 이 있 는 충분 한 조건 은 gcd (a, n) = 1 이 고 이때 역 원 이 유일 하 게 존재 한다.  역 원 의 의미: 모 n 의 의미 에서 1 개의 수 a 가 역 원 x 가 있 으 면 a 를 곱 하기 x 에 해당 한다.
다음은 역 원 을 구 하 는 몇 가지 방법 을 드 리 겠 습 니 다.
1. 반복 해서 해법 찾기
주어진 모드 m 와 역 구 해 야 할 수 x, 직접 폭력 매 거 1 ~ m - 1  x * i = 1 (mod m) 이 있 는 지 확인
이런 알고리즘 은 폭력, 대조, 모드 가 비교적 작고 역수 가 적은 상황 을 응용 하고 쓸 수 있다  시간 복잡 도 O (m)
2 확장 유클리드 알고리즘
주어진 모드 m, a 의 역 은 x = 1 (mod m) 에 해당 합 니 다.  이 방정식 은 x - my = 1 로 바 뀔 수 있다.  그 다음 에 이원 일차 방정식 을 구 하 는 방법 을 사용 하여 유클리드 알고리즘 을 확장 하여 x0, y0 과 gcd 를 구 했다.  gcd 가 1 인지 확인 하기  gcd 가 1 이 아 닌 것 은 역 원 이 존재 하지 않 는 다 는 것 을 의미한다.  1 이면 x0 에서 0 ~ m - 1 범위 로 조정 하면 됩 니 다.

void ext_gcd(int a,int b,int &d,int &x,int &y){
    if (b==0){
        d=a;x=1;y=0;
        return;
    }
    ext_gcd(b,a%b,d,y,x);//  
    y-=a/b*x;
}
int main(){
    scanf("%d%d",&m,&n);// m  n   
    ext_gcd(m,n,d,x,y);
    printf("%d
",(x+n)%n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
이런 알고리즘 은 효율 이 비교적 높 고 상수 가 비교적 적 으 며 시간 복잡 도 는 O (ln n) 이다.
3. 페 마 의 작은 정리 와 오로라 의 정리
모드 가 소수 p 인 상황 에서 페 르 마 의 작은 정리 가 있다.  a^(p-1)=1（mod p）  그럼 a ^ (p - 2) = a ^ - 1 (mod p)  즉 a 의 역 원 은 a ^ (p - 2)
그러나 모드 가 소수 p 가 아 닌 상황 에서 오로라 의 정리 가 있다.  a^phi(m)=1（mod m） (a⊥m)  같은 이치 a ^ - 1 = a ^ (phi (m) - 1)
따라서 역 원 x 는 빠 른 멱 으로 x = a ^ (phi (m) - 1) 를 구 할 수 있다.
그런데 또 문제 가 있 는 것 같은 데?어떻게 a 에 역 원 이 있 는 지 판단 합 니까? gcd 의 상호 품질 여 부 를 다시 한 번 판단 해 주 시 겠 습 니까?  차라리 확장 유클리드 알고리즘 을 사용 하 는 게 낫 겠 어 요 > <
사실 문 제 는 매우 간단 하 다. 이것 이 역 원 인지 아 닌 지 직접 판단 하면 된다.  역 원 의 성질 을 검사 하여 구 한 지수 x 와 a 의 상승 이 1 인지 아 닌 지 를 보면 된다.
이 알고리즘 은 복잡 도가 O (log 2 n) 이다.  몇 차례 의 테스트 에서 상수 가 위의 방법 보다 큰 것 같다.
4 O (n) 구 1 ~ n 역 원 표
가끔 이런 문제 에 부 딪 히 기도 한다.  모 질 수 p 에서 1 ~ n 역 원 n < p 구하 기
이 문 제 는 매우 훌륭 한 알고리즘 이 있 는데 다음 과 같은 추론 을 바탕 으로 한다.  역원  p%i+[p/i]*i=p  a = p% i, b = [p / i]  a+b*i=p  a+b*i=0（mod p）  b*i=-a（mod p）  i^-1=-b/a  즉 i 의 역 원 은: - [p / i] * (p% i) ^ - 1  한편, p% i ＜ i 는 2 배 에서 n 으로 역 원 을 구 할 수 있 으 며, i 를 구하 기 전에 p% i 는 반드시 구 할 수 있다.  이렇게 하면 O (n) 가 모든 역 원 을 구 할 수 있다.  (초기 화 1 ^ (- 1) = 1)  코드 는 다음 과 같다.

    inv[1]=1;
    fo(i,2,n)
        inv[i]=(long long)(p-p/i)*inv[p%i]%p;

1
2
3
위의 이런 알고리즘 을 제외 하고 몇 가지 O (n) 의 역 원 표 구법 도 있 지만 위의 이런 방법 이 간편 하지 않다.  A 는 먼저 O (n) 에서 1 을 미리 처리 할 수 있 습 니 다! ~n! 그리고 O (log n) 의 복잡 도 로 n 을 구 해!의 역원  그리고 O (n) 에서 i 를 처리 할 수 있 습 니 다!의 역원 (1 / i! = (i + 1) / (i + 1)! 거꾸로 밀 면 된다)  다음은 O (n) 에서 모든 i 의 역 원 1 / i = (i - 1) 를 구 할 수 있 습 니 다! /i!  단계 곱 하기 역 원 의 문 제 를 동시에 미리 처리 해 야 한다. 이런 방법 으로 역 원 표를 구 할 수 있다.
이런 방법 은 확장 성 이 비교적 강하 기 때문에 이런 방법 으로 한 서열 에 있 는 모든 요소 (요소 접두사 적) 의 역 원 을 구 할 수 있 고 복잡 도 역시 O (n) 로 하나의 단독 계산 역 원 효율 보다 더욱 좋다.
B 는 선형 체 법 을 사용 할 수 있다.역 원 은 적 함수 이기 때문에 합 수의 역 원 은 O (1) 로 계산 할 수 있 고 질 수의 역 원 은 O (log n) 의 복잡 도 로 구 할 수 있다.n 내 질 수 는 n / log n 개 정도 있 기 때문이다.총 복잡 도도 O (n)
디버그 문제
마지막 으로 어떻게 디 버 깅 하 는 지, 구 하 는 역 원 이 정확 한 지 간단히 말 하 겠 습 니 다.  아니면 위 에서 말 한 것 처럼 원수 와 곱 하기 가 1 인지 직접 테스트 하면 된다.
여기 서 한 마디 더 하 겠 습 니 다. 빠 른 속도 계산법 이 정확 한 지 어떻게 검사 합 니까?  마음대로 1 개의 질 수 p 를 찾 아 a ^ (p - 1)% p 가 모두 1 인지 검사 하면 됩 니 다 (1 < = a ＜ p)