高速べき乗アルゴリズムテンプレート|余剰演算

高速べき乗アルゴリズムテンプレート
m k m^k mk%p、時間複雑度O(log k k k)を求めます.

int qmi(int m, int k, int p)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

b&1について「&」の美名は「位と」と呼ばれています.x&yは、バイナリxとyの各ビットがそれぞれ「演算」を行った結果である.演算、すなわち両方が1の場合に1を返します.そうでなければ0を返します.ではb&1バイナリはb=1011=0001 b&1=0001を表す
1(バイナリ)の上位数桁がすべて0であるため,bバイナリの最下位が1である場合にのみ,b&1は1を返す.とても巧みで、しかも速いです.

int quickPower(int a, int b)//  a b  
{
    int ans = 1, base = a;//ans   ，base a^(2^n)
    while(b > 0)//b          ，       
    {
        if(b & 1)//&    ，b&1  b            1，   ：
            ans *= base;// ans     a^(2^n)

        base *= base;//base  ， a^(2^n)  a^(2^(n+1))
        b >>= 1;//   ，b    ， 101  10（     1   ），10010  1001。  b                  。    b & 1    
    }
    return ans;
}

余剰演算高速べき乗は、余剰演算と組み合わせることが多い.ここでも少し話します.
余剰演算には、次のような使いやすい性質があります.
(A+B) mod b = (A mod b + B mod b) mod b (A×B) mod b = ((A mod b) × (B mod b))mod b証明は簡単なので、自分を説得するならペンを取ってみましょう
そこで高速べき乗の过程の中で実际にプログラミングあるいは试合の时できるだけ*=%mと别れて书くことができて私に何を闻かないでください私もどうしてこのように洛谷のコンパイラの上でできるだけ别れて书くことを知りませんさもなくばいくつかのテストのサンプルは通じません

			  1：
            ans *= base;
            ans %= m;
            
			 base *= base;
       		 base %= m;
              :2：
            ans = ans * base % m;
            base = base * base % m;

【注意事項】1、一歩の演算を行うたびに得られた答えをpに型を取ります.そうしないと28点しかありません.
2、b m p ansはlong long型変数として定義しなければならない.そうしないと42点しかない.
3、演算中に答えを型にすれば十分だと思わないでください.答えを出力するときは、最終的な答えをpにもう一度型を取ることを忘れないでください.そうしないと84点しかありません.
4、以上の注意事項を組み合わせた高速べき乗プログラムで100点を得ることができます.

  while(b > 0)
    {
        if(b & 1)
        {
            ans *= base;
            ans = ans * base
            ans %= m;
        }

        base *= base;
        base %= m;
        b >>= 1;
    }

このようにして最後の結果が「最後まで乗って、残りを取る」という結果と同じであることが保証されます.ケース