ARC111A_Simple_Math2

Question

ARC111Aについて

ARC111A_Simple_Math2

正整数 N,M が与えられます。⌊10^N/M⌋ を Mで割った余りを求めてください。

こちらの問題について考えています。
解くことができなかったため、他の方の解答を参考にしていますが、実装で理解できない部分があります。
powbodのmethod内で &演算とn>>=演算をしていますが、これらの演算がどのような意味を持っているのかがわかっていません。
おわかりの方がいましたら教えていただきたいです。よろしくお願いいたします。

admin解説

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// a^n % modを求める
int powmod(int a, ll n, int mod) {
    int pm = 1;
    while (n > 0) {
        if (n & 1) pm = (ll)pm * a % mod; # ①
        a = (ll)a * a % mod;
        n >>= 1; #　②
    }
    return pm;
}


int main() {
    ll n, m;
    cin >> n >> m;
    printf("%d\n", powmod(10, n, m * m) / m % m);
    return 0;
}

Answer 1

繰り返し二乗法と呼ばれる高速化のテクニックです

Answer 2

「繰り返し2乗法」と呼ばれるもので、a^nをO(log n)で求める方法です。

Answer 3

こちらの記事を見て理解ができました。
繰り返し二乗法に関する記事