解法

数学。

$\rm{ones}(n) = \overbrace{111\dots 1}^{n \; \text{times}}$とする。 lcmを求めるので、まずは$\rm{lcm}(\rm{ones}(a), \rm{ones}(b)) = \rm{ones}(a) \cdot \rm{ones}(b) / \rm{gcd}(\rm{ones}(a), \rm{ones}(b))$。 $a \le b$として、$\rm{gcd}(\rm{ones}(a), \rm{ones}(b)) = \rm{gcd}(\rm{ones}(b) \bmod \rm{ones}(a), \rm{ones}(a))$であるが、$\rm{ones}(b) \bmod \rm{ones}(a) = \rm{ones}(b \bmod a)$であるので、$\rm{gcd}(\rm{ones}(a), \rm{ones}(b)) = \rm{ones}(\rm{gcd}(a,b))$となる。 また、$b \bmod d = 0$のとき、$\rm{ones}(b) / \rm{ones}(d)$は、$\underbrace{\overbrace{00 \dots 0}^{\frac{b}{d}-1 \; \text{times}}1\overbrace{00 \dots 0}^{\frac{b}{d}-1 \; \text{times}}1\dots \overbrace{00 \dots 0}^{\frac{b}{d}-1 \; \text{times}}1}_{d \; \text{times}}$と$10$進数表記される整数である。

これらは、行列累乗法で高速に計算できる。

ここで用いた$\rm{ones}(-)$の性質は、 $\overbrace{111 \dots 1}^{b \; \text{times}} = \overbrace{111 \dots 1}^{a \; \text{times}}\overbrace{111 \dots 1}^{a \; \text{times}}\dots \overbrace{111 \dots 1}^{a \; \text{times}}\overbrace{111 \dots 1}^{c \; \text{times}}$ ($c \lt a$)とすると、 $\overbrace{111 \dots 1}^{b \; \text{times}} = (\overbrace{111 \dots 1}^{a \; \text{times}}) \times ( \overbrace{00 \dots 0}^{a-1 \; \text{times}}1\overbrace{00 \dots 0}^{a-1 \; \text{times}}1\dots \overbrace{00 \dots 0}^{a-1 \; \text{times}}1 \overbrace{000 \dots 0}^{c \; \text{times}}) + \overbrace{111 \dots 1}^{c \; \text{times}}$となることから確認できる。 $c = b \bmod a$である。

実装

boostの行列なりを使いたかったが、mod取るのが面倒そうなので自前。 ちょっと汚くなってしまった。

#include <iostream>
#include <vector>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b) { if (b < a) swap(a,b); while (a) { ll c = a; a = b % c; b = c; } return b; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll powi(ll x, ll y, ll p) { x = (x % p + p) % p; ll z = 1; for (ll i = 1; i <= y; i <<= 1) { if (y & i) z = z * x % p; x = x * x % p; } return z; }
ll inv(ll x, ll p) { assert ((x % p + p) % p != 0); return powi(x, p-2, p); }

ll a, b, m; // global

vector<vector<ll> > operator * (vector<vector<ll> > const & p, vector<vector<ll> > const & q) { int n = p.size(); vector<vector<ll> > r(n, vector<ll>(n)); repeat (y,n) { repeat (z,n) { repeat (x,n) { r[y][x] += p[y][z] * q[z][x] % m; r[y][x] %= m; } } } return r; }
vector<ll> operator * (vector<vector<ll> > const & p, vector<ll> const & q) { int n = p.size(); vector<ll> r(n); repeat (y,n) { repeat (z,n) { r[y] += p[y][z] * q[z] % m; r[y] %= m; } } return r; }
vector<vector<ll> > unit_matrix(int n) { vector<vector<ll> > e(n, vector<ll>(n)); repeat (i,n) e[i][i] = 1; return e; }
vector<vector<ll> > mul (vector<vector<ll> > const & p, vector<vector<ll> > const & q) { return p * q; }
template <typename T, typename F> T powt(T x, ll y, T unit, F f) { T z = unit; for (ll i = 1; i <= y; i <<= 1) { if (y & i) z = f(z, x); x = f(x, x); } return z; }

int main() {
    cin >> a >> b >> m;
    ll d = gcd(a, b);
    vector<vector<ll> > f(2, vector<ll>(2));
    vector<vector<ll> > g(2, vector<ll>(2));
    vector<ll> e(2);
    f[0][0] = 10; f[0][1] = 1;
    f[1][0] =  0; f[1][1] = 1;
    g[0][0] = powi(10,d,m); g[0][1] = 1;
    g[1][0] =            0; g[1][1] = 1;
    e[0] = 0;
    e[1] = 1;
    a = (powt(f,   a, unit_matrix(2), &mul) * e)[0];
    b = (powt(g, b/d, unit_matrix(2), &mul) * e)[0];
    cout << a * b % m << endl;
    return 0;
}