A - Sequence with Digits

本文主要是介绍A - Sequence with Digits，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：由递推式 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;
}

这篇关于A - Sequence with Digits的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！