上手に整理すれば、とてもシンプルな問題!
問題概要
正の整数 が与えられる。
を
で割った商
を
で割ったあまりを求めよ。
制約
考えたこと
で割るような操作を 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; }