型取り演算のまとめ-数論
導入プログラミングコンテストではかなりの部分の問題の結果が膨大すぎて整数タイプが記憶できず、型取りの結果だけを出力するように要求されることが多い. 例えば(a+b)%p、a+bの結果を記憶できない場合は、型を取りに行きます.結果は明らかに違います.オーバーフローを防ぐために、aを型取り、bを型取り、合計し、出力した結果は同じです. a mod bはaをbで割った剰余を表す.次の式があります. (a + b) % p = (a%p + b%p) %p (a - b) % p = ((a%p - b%p) + p) %p (a * b) % p = (a%p)*(b%p) %p
除算型については、直接型を取ることはできません.詳細は逆元を参照してください.
クイックべき乗型取り
クイック乗算型取りa*b%modを計算すると、a*bがデータの範囲を超えて計算されることが多い.この場合、高速乗算法を用いることで上記の問題を解決できる. 高速乗算の原理は数を多項式加算に分解することである.例:30*14=30*(1110)2=30*(2^3)1+30(2^2)1+30(2^1)1+30(2^0)*0=240+120+60=420
逆元/数論の逆数-逆数型取り演算用逆元
逆メタ概念の導入
(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いくつかの問題については、中間過程で余剰を求めなければなりません.そうしないと、数字が大きすぎて、パソコンが保存できません.もしこの計算式に除算が現れたら、私たちはこの計算式に対して計算できないのではないでしょうか.この場合、逆元が必要になるa*inv(a)=1またa*b=1(mod p)bに対してはaの逆数とは限らないが、余剰を求めれば、bをaの逆数と見なし、bをaのpに関する逆元と呼ぶことができる.b=inv(a)と記す.前提条件aとpは互いに質を交換して、aはやっとpの逆元についてそれでは除法に対して型を取ることに対して私達はよく解決しました.(a/b) % p = (a * inv(a) ) % p = (a % p * inv(a) % p) % p
具体的な実装
フェルマのののていり
定理内容は,pが素数,gcd(a,p)=1であればa^(p−1)≡1(mod p)−a^(p−2)≡1/a(mod p)a^(p−2)≡inv(a)(mod p)inv(a)=a^(p−2)−時間複雑度O(logn)である.
拡張ユークリッドアルゴリズム
式a∗x+b∗y=gcd(a,b).a,bが互いに質的で解がある場合、a∗x+b∗y=1がある.aにbの逆元について要求すると、私たちはこのように見ることができます.a*x%b+b*y%b=1%b a*x%b=1%b a*x=1(mod b)から分かるように,拡張ユークリッドアルゴリズムは逆元を実現できる.
例題
hdu-1576-A/B
クイックべき乗型取り
typedef long long LL;
LL pow_mod(LL a,LL b,LL p){//
LL ans=1,base=a;
while(b>0){
if(b&1) //n%2==1
ans=ans*base%p;
base=base*base%p;
b>>=1;// b/=2
}
return ans;
}クイック乗算型取り
typedef long long LL;
LL q_mul(LL a, LL b, LL p){//
LL ans = 0;
while (b){
if(b&1LL) ans=(ans+a)%p;
//or ans=(ans+(b%2*a)%p)%p;
a = (a +a) % p;
b >>= 1;
}
return ans;
}逆元/数論の逆数-逆数型取り演算用逆元
逆メタ概念の導入
(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いくつかの問題については、中間過程で余剰を求めなければなりません.そうしないと、数字が大きすぎて、パソコンが保存できません.もしこの計算式に除算が現れたら、私たちはこの計算式に対して計算できないのではないでしょうか.この場合、逆元が必要になるa*inv(a)=1またa*b=1(mod p)bに対してはaの逆数とは限らないが、余剰を求めれば、bをaの逆数と見なし、bをaのpに関する逆元と呼ぶことができる.b=inv(a)と記す.前提条件aとpは互いに質を交換して、aはやっとpの逆元についてそれでは除法に対して型を取ることに対して私達はよく解決しました.(a/b) % p = (a * inv(a) ) % p = (a % p * inv(a) % p) % p
具体的な実装
フェルマのののていり
定理内容は,pが素数,gcd(a,p)=1であればa^(p−1)≡1(mod p)−a^(p−2)≡1/a(mod p)a^(p−2)≡inv(a)(mod p)inv(a)=a^(p−2)−時間複雑度O(logn)である.
typedef long long LL;
LL fermat(LL a,LL p)// a b
{
return pow_mod(a,p-2,p);
}拡張ユークリッドアルゴリズム
式a∗x+b∗y=gcd(a,b).a,bが互いに質的で解がある場合、a∗x+b∗y=1がある.aにbの逆元について要求すると、私たちはこのように見ることができます.a*x%b+b*y%b=1%b a*x%b=1%b a*x=1(mod b)から分かるように,拡張ユークリッドアルゴリズムは逆元を実現できる.
typedef long long LL;
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){//
if (!b) {d = a, x = 1, y = 0;}
else{
ex_gcd(b, a % b, y, x, d);
y -= x * (a / b);
}
}
LL inv(LL t, LL p){// ， -1
LL d, x, y;
ex_gcd(t, p, x, y, d);
return d == 1 ? (x % p + p) % p : -1;
}例題
hdu-1576-A/B