2017.8.22 ACM 训练赛 题解

#include <bits/stdc++.h>
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;

LL mul(LL a, LL b, LL m) {
    LL ret = 0;
    while (b) {
        if (b & 1) {
            ret += a;
            if (ret >= m) ret -= m;
        }
        a += a;
        if (a >= m) a -= m;
        b >>= 1;
    }
    return ret;
}


LL pown(LL x, LL n, LL MOD) {
    LL ret = 1; x %= MOD;
    while (n) {
        if (n & 1) ret = mul(ret, x, MOD);
        x = mul(x, x, MOD);
        n >>= 1;
    }
    return ret;
}

LL T, n, m;
int main() {
    cin >> T;
    while (T--) {
        cin >> n >> m;
        cout << (pown(10, n, m * 9) + m * 9 - 1) % (m * 9) / 9 << endl;
    }
}