爱站程序员基地传送
Let\’s define the following recurrence:
an+1=an+minDigit(an)⋅maxDigit(an).an+1=an+minDigit(an)⋅maxDigit(an).
Here minDigit(x)minDigit(x) and maxDigit(x)maxDigit(x) are the minimal and maximal digits in the decimal representation of xx without leading zeroes. For examples refer to notes.
Your task is calculate aKaK for given a1a1 and KK.
Input
The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of independent test cases.
Each test case consists of a single line containing two integers a1a1 and KK (1≤a1≤10181≤a1≤1018, 1≤K≤10161≤K≤1016) separated by a space.
Output
For each test case print one integer aKaK on a separate line.
Example
Input
[code]81 4487 1487 2487 3487 4487 5487 6487 7
Output
[code]42487519528544564588628
Note
a1=487a1=487
a2=a1+minDigit(a1)⋅maxDigit(a1)=487+min(4,8,7)⋅max(4,8,7)=487+4⋅8=519
a3=a2+minDigit(a2)⋅maxDigit(a2)=519+min(5,1,9)⋅max(5,1,9)=519+1⋅9=528
a4=a3+minDigit(a3)⋅maxDigit(a3)=528+min(5,2,8)⋅max(5,2,8)=528+2⋅8=544
a5=a4+minDigit(a4)⋅maxDigit(a4)=544+min(5,4,4)⋅max(5,4,4)=544+4⋅5=564
a6=a5+minDigit(a5)⋅maxDigit(a5)=564+min(5,6,4)⋅max(5,6,4)=564+4⋅6=588
a7=a6+minDigit(a6)⋅maxDigit(a6)=588+min(5,8,8)⋅max(5,8,8)=588+5⋅8=628
题意：（计算规则直接看Note就能懂），题目要求输出数字a进行（K-1）次计算后的结果（因为k==1时就是a本身，所以本质上是对a进行k-1次计算）。不加思考的第一反应当然就是根据计算规则暴力计算咯，想要程序看上去简洁一点还可以写个函数。但很显然，数字a很很很很很大，计算次数k也很很恨很很大，只要你敢暴力，它就敢超时。所以我们需要找到其中的规律，计算中有一个很致命的点在max*min，如果我的min==0，那么这部分也就等于0，经过一次计算以后a值仍然不变，同样计算一万次一千万次以后也不会变，所以在暴力过程，检测到min==0了， 就可以退出计算了。
[code]#include<iostream>#include<algorithm>#include<cstring>typedef long long ll;using namespace std;ll ans(ll a, ll k){if(k==1) return a;ll num = a;int mina=a%10, maxa=a%10;while(num && mina){int x = num%10;if(x<mina) mina = x;if(x>maxa) maxa = x;num /= 10;}if(mina==0) return a;return ans(a+mina*maxa, k-1);}int t;ll a, k;int main(){scanf(\"%d\", &t);while(t--){scanf(\"%lld%lld\", &a, &k);printf(\"%lld\\n\", ans(a, k));}return 0;}
