数論を唱える逆―

回転:http://www.cnblogs.com/linyujun/p/5194184.html
先に求余概念を導入します.
(a+b)%p=(a%p+b%p)%p(はい)
(a-b)%p=(a%p-b%p)%p(はい)
(a＊b)%p=(a%p*b%p)%p(はい)
(a/b)%p=(a%p/b%p)%p(間違い)
なぜ割り算が間違っていますか?
正しいことを証明するのは難しいです.間違いを証明するのは反例を一つ挙げてください.
(100/50)%20=2≠(100%20)/(50%20)%20=0
いくつかの問題に対して、私達は中間過程で剰余を求めなければなりません.でないと、数字が大きすぎて、コンピューターが保存できません.もしこの式に割り算ができたら、私達はこの式に対して計算できなくなりますか?
答えはもちろんNO(>o
この時は逆元が必要です.
知っています
もし
a＊x=1
xはaの逆数で、x=1/aです.
しかし、aは1ではないなら、xは小数である.
その数論の中では、ほとんどの状況が残りますから、今は問題が変わりました.
a＊x=1(mod p)
xはきっと1/aに等しいですか?
必ずしも
だからこの時、私達はxをaの逆数と見なして、ただ1つの余分な条件をプラスしただけで、だからxはaについてpの逆元と言います.
例えば2*3%5=1であれば、3は2について5の反元、あるいは2と3について5について互いに反元となります.
この3の効果は1/2の効果と同じですか?だからカウントダウンと言います.
aの逆元はinv(a)で表します.
じゃ(a/b)%p=(a*inv(a))p=(a%p*inv(a)%p)p
(ここで自分で書いたのは、なぜ(a/b)%p=(a*inv(a)%pの一般的な説明)bに乗算逆元があると仮定します.つまりmとの相互作用(充填条件)です.cはbの逆元、つまりb*cはmodm 1(modm)に等しいと仮定します.a/b=(a/b)を逆モードで乗じます.
これで割り算を完全に掛け算に変換します(・.ω・)かけ算が超簡単
本編開始
逆元はどうやって求めますか
(言い忘れました.aとpは互いに質的で、aはpに関する反元があります)
方法1:
ファマは、数学者になりたくない数学者はいい数学者ではないと言っていました.
馬子の定理を欠く
a^(p-1)＝1(mod p)
両方をaで割る
a^(p-2)＝1/a(mod p)
なんですか?これは数論です.また1/aも書きます.
a^(p-2)を書くべきです.
だからinv(a)=a^(p-2)(mod p)
これは高速べき乗でお願いします.複雑度O(logn)̀_•́)湖南省にある地名

 1 LL pow_mod(LL a, LL b, LL p){//a b    p 
 2     LL ret = 1;
 3     while(b){
 4         if(b & 1) ret = (ret * a) % p;
 5         a = (a * a) % p;
 6         b >>= 1;
 7     }
 8     return ret;
 9 }
10 LL Fermat(LL a, LL p){//   a  b    
11         return pow_mod(a, p-2, p);
12 }

方法二:
ユークリッドを拡張するアルゴリズムを使います.
ユークリッドを広げたことを覚えていますか?
a＊x+b*y=1
abが互质であれば、解があります.
この解のxはaのbに対する反元である.
yとはbのaに対する反元です.
なぜですか
見てください.両方を同時にお願いします.
a*x%b+b*y%b=1%b
a＊x%b=1%b
a＊x=1(mod b)
ほら、出てきたよ!!(/≧▽≦/)
xはaのbに対する逆の元です.
逆に証明できるy
コードを添付:

 1 #include
 2 typedef long long LL;
 3 void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
 4     if (!b) {d = a, x = 1, y = 0;}
 5     else{
 6         ex_gcd(b, a % b, y, x, d);
 7         y -= x * (a / b);
 8     }
 9 }
10 LL inv(LL t, LL p){//     ，  -1 
11     LL d, x, y;
12     ex_gcd(t, p, x, y, d);
13     return d == 1 ? (x % p + p) % p : -1;
14 }
15 int main(){
16     LL a, p;
17     while(~scanf("%lld%lld", &a, &p)){
18         printf("%lld
", inv(a, p));
19     }
20 }

方法三:
pが素数の場合はinv(a)=(p-p/a)*inv(p%a)%pがあります.
これはなぜ正しいですか?
見たくないと証明した子供は跳べます...(￣0￣)
証明:x=p%aを設定し、y=p/aはx+y*a=p(x+y*a)%p=0をx%p=(-y)*a%p x*inv(-y)p=(a)=p inv(a)=(p-y)*inv(x)%pを持っています.
そして1まで再帰します.1の逆元は1です.
コード:

 1 #include
 2 typedef long long LL;
 3 LL inv(LL t, LL p) {// t  p   ，  :t   p，       t%p   
 4     return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;
 5 }
 6 int main(){
 7     LL a, p;
 8     while(~scanf("%lld%lld", &a, &p)){
 9         printf("%lld
", inv(a%p, p));
10     }
11 }

この方法は単一の逆要素を求めることに限らず、前の2つよりも良く、O(n)の複雑さの中からn個の数の逆要素を算出することができる.
再帰は上の書き方です.記憶性を加えて再帰すればいいです.
このように書いてください

 1 #include
 2 const int N = 200000 + 5;
 3 const int MOD = (int)1e9 + 7;
 4 int inv[N];
 5 int init(){
 6     inv[1] = 1;
 7     for(int i = 2; i < N; i ++){
 8         inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
 9     }
10 }
11 int main(){
12     init();
13 }

また新しい知識を勉強しましたo(*≧▽≦)ツ嬉しいです.
逆元詳細は以下の通りです.http://blog.csdn.net/acdreamers/article/details/8220787