题意:由递推式
a
n
+
1
=
a
n
+
m
i
n
D
i
g
i
t
(
a
n
)
⋅
m
a
x
D
i
g
i
t
(
a
n
)
a_{n+1}=a_n+minDigit(a_n)⋅maxDigit(a_n)
an+1=an+minDigit(an)⋅maxDigit(an),其中
m
i
n
D
i
g
i
t
(
a
n
)
minDigit(a_n)
minDigit(an),
m
a
x
D
i
g
i
t
(
a
n
)
maxDigit(a_n)
maxDigit(an)分别为
a
n
a_n
an中最小的一位数和最大的一位数,求
a
k
a_k
ak的值。
做法:题目的数据范围非常大,显然直接暴力是不可取的。对于这种递推式的题,有时结果会有一定的规律性,可以打表肉眼观察,也可以通过严格的数学推理证明。在本题中,我使用了打表的方法,不难看出当k达到一定值时结果不会发生改变,因为最小的一位是0,0乘任何数都得0,所以结论就很显然了。由于本人数论水平较低,就不通过数学推理证明了,据说 codeforces上有严格的证明,有兴趣的同学自行查看。
代码:
#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; typedef pair <int, int> PII; const int N = 1e5 + 10; const ll mod = 1e9 + 7; int t; ll n, k; int main() { cin >> t; while(t--) { cin >> n >> k; for(int i = 1; i <= min(k - 1, 1000ll); i++) { ll tmp = n, maxn = 0, minn = 9; while(tmp) { maxn = max(maxn, tmp % 10); minn = min(minn, tmp % 10); tmp /= 10; } n += maxn * minn; } printf("%lld\n", n); } return 0; }