#include <climits> #include <cstdio> #include <unordered_map> #include <vector> using namespace std; using i64 = long long; template <class T1, class T2, class T3> inline void add(T1& a, T2 b, T3 mod) { a += b; while (a > mod) a -= mod; } template <class T> inline T div_10(T x) { return x <= INT_MAX ? (x * 1717986919LL) >> 34 : x / 10; // The magic number is given by g++. } template <class T> inline T mod_10(T x) { T res = div_10(x); return x - res * 10; } inline int max_digit(i64 x) { int mx = 0; while (x > 0) { int digit = mod_10(x); mx = (digit > mx ? digit : mx); x = div_10(x); } return mx; } int main() { i64 pos, mod, n; scanf("%lld %lld %lld", &pos, &mod, &n); if (mod <= 1e8) { int len = 1, id = -1, curr = pos, md = mod; vector<int> been { curr }; unordered_map<int, int> idx { { curr, 0 } }; for (i64 i = 1; i < n; ++i) { add(curr, max_digit(curr), md); if (idx.find(curr) != idx.end()) { id = idx[curr]; break; } idx[curr] = len++; been.emplace_back(curr); } if (id == -1) printf("%d\n", curr); else printf("%d\n", been[(n - id - 1) % (len - id) + id]); return 0; } while (n-- > 1) add(pos, max_digit(pos), mod); printf("%lld\n", pos); return 0; } // 1, 1, 4, 5, 2, 4, 5, 2, ... // id = 2 // len = 5 // n = 9: 4