AtCoder ARC 111 A - Simple Math 2 (緑色, 300 点)

上手に整理すれば、とてもシンプルな問題！

• 問題へのリンク

問題概要

正の整数 が与えられる。

を で割った商 を で割ったあまりを求めよ。

制約

• 
• 

考えたこと

で割るような操作を 2 回しているので、 を で割った余りを考えるとよいのだろうなというあたりをつける。

を で割ったときの商を 、あまりを として、

とおく。さらに、 を で割ったときの商を 、あまりを とすると

と表せることになる。さて、このとき、 と表せることから、次のことが読み取れる。

---

• を で割ったときの商は に一致する
• さらに、 を で割ったあまりは に一致する
• したがって、求める値は である

---

よって、この問題は「 を で割ったあまりを で割った商」を求めることで解ける。

計算量は となる。

コード

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

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    long long N, M;
    cin >> N >> M;
    cout << modpow(10LL, N, M * M) / M << endl;
}