fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <queue>
  12. #include <ctime>
  13. #include <cassert>
  14. #include <complex>
  15. #include <string>
  16. #include <cstring>
  17. #include <chrono>
  18. #include <random>
  19. #include <bitset>
  20. using namespace std;
  21.  
  22. #ifdef LOCAL
  23. 	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
  24. #else
  25. 	#define eprintf(...) 42
  26. #endif
  27.  
  28. using ll = long long;
  29. using ld = long double;
  30. using uint = unsigned int;
  31. using ull = unsigned long long;
  32. template<typename T>
  33. using pair2 = pair<T, T>;
  34. using pii = pair<int, int>;
  35. using pli = pair<ll, int>;
  36. using pll = pair<ll, ll>;
  37. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  38.  
  39. #define pb push_back
  40. #define mp make_pair
  41. #define all(x) (x).begin(),(x).end()
  42. #define fi first
  43. #define se second
  44.  
  45. double startTime;
  46. double getCurrentTime() {
  47. 	return ((double)clock() - startTime) / CLOCKS_PER_SEC;
  48. }
  49.  
  50. const ll INF = (ll)1e18 + 100;
  51. ll add(ll x, ll y) {
  52. 	return min(x + y, INF);
  53. }
  54.  
  55. const int L = 19;
  56. const int A = 10;
  57. ll p10[L];
  58. pll g[L][A][A];
  59.  
  60. ll getMaxDig(ll x) {
  61. 	ll res = 0;
  62. 	while(x > 0) {
  63. 		res = max(res, x % 10);
  64. 		x /= 10;
  65. 	}
  66. 	return res;
  67. }
  68.  
  69. void precalc() {
  70. 	p10[0] = 1;
  71. 	for (int i = 1; i < L; i++)
  72. 		p10[i] = p10[i - 1] * 10;
  73. 	for (int len = 1; len < L; len++) {
  74. 		for (int X = 0; X < A; X++)
  75. 			for (int Y = 0; Y < A; Y++) {
  76. 				if (X == 0 && Y == 0) {
  77. 					g[len][X][Y] = mp(INF, 0);
  78. 					continue;
  79. 				}
  80. 				ll t = 0, lst = Y;
  81. 				if (len == 1) {
  82. 					while(lst < A) {
  83. 						t++;
  84. 						lst += max(lst, (ll)X);
  85. 					}
  86. 					g[len][X][Y] = mp(t, lst - A);
  87. 				} else {
  88. 					for (ll c = 0; c < A; c++) {
  89. 						pll cur = g[len - 1][max((ll)X, c)][lst];
  90. 						t = add(cur.first, t);
  91. 						lst = cur.second;
  92. 					}
  93. 					g[len][X][Y] = mp(t, lst);
  94. 				}
  95. 			}
  96. 	}
  97. }
  98.  
  99. map<ll, ll> mem;
  100.  
  101. int main()
  102. {
  103. 	startTime = (double)clock();
  104. //	freopen("input.txt", "r", stdin);
  105. //	freopen("output.txt", "w", stdout);
  106.  
  107. 	precalc();
  108.  
  109. 	ll S, M, T;
  110. 	scanf("%lld%lld%lld", &S, &M, &T);
  111. 	T--;
  112. 	while(T > 0) {
  113. 		if (mem.count(S)) {
  114. 			ll P = mem[S] - T;
  115. 			T %= P;
  116. 			if (T == 0) break;
  117. 		}
  118. 		mem[S] = T;
  119. 		int len = L - 1;
  120. 		while(len > 0) {
  121. 			ll Y = S % p10[len];
  122. 			if (Y >= A) {
  123. 				len--;
  124. 				continue;
  125. 			}
  126. 			if (S - Y + p10[len] > M) {
  127. 				len--;
  128. 				continue;
  129. 			}
  130. 			ll X = getMaxDig(S / p10[len]);
  131. 			pll cur = g[len][X][Y];
  132. 			if (cur.first > T) {
  133. 				len--;
  134. 				continue;
  135. 			}
  136. 			T -= cur.first;
  137. 			S -= Y;
  138. 			S += p10[len];
  139. 			S += cur.second;
  140. 			S %= M;
  141. 			break;
  142. 		}
  143. 		if (len == 0) {
  144. 			ll X = getMaxDig(S);
  145. 			T--;
  146. 			S = (S + X) % M;
  147. 		}
  148. 	}
  149. 	printf("%lld\n", S);
  150.  
  151. 	return 0;
  152. }
  153.  
Success #stdin #stdout 0s 4284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/NkhclY
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!