[code source] I have a big head for a problem every day

2022.05.23

Topic link ： I have a big head - subject - Daimayuan Online Judge

Title Description ：

Xiao Ming, who loves mathematics, is back hot ！ After reading the last time everyone's solution to the problem, I think I'm really stupid , At the same time, it attracted the ridicule of Xiao Hong, who is also a math lover , Xiao Ming, who has a strong self-esteem, is very angry , Then make a bet with Xiao Hong , Let Xiao Hong write a math problem for Xiao Ming , If Xiao Ming can write it in a week , Xiao Hong invited him to eat next week's crazy Thursday , If you can't do it, Xiao Ming will ask her to go crazy on Thursday .

But this problem is really too difficult , Xiao Ming locked himself in his room and couldn't think of it for a week , Tomorrow is the deadline for the bet , Xiao Ming really wants to eat KFC, So he thought of asking you for help again , And promised to ask Xiao Hong as long as he helped him write this problem KFC Give you half .

Xiao Hong set up two functions  f(x) and g(x,m) .

f(x) Is defined as follows ：

such as ：f(2013)=(2013∗13∗13∗3)mod2014

g(x,m) Is defined as follows ：

such as g(x,2)=f(f(x)) 

Now? , I want you to find out Value .

 

in order to KFC, Spell it. ！

Input format

The first line has a number T (1≤T≤20), There is a total of TT Group data . Next TT There are two numbers in a row x,mx,m(1≤x,m≤10^9), representative g(x,m) Two parameters of

Output format

Output a number for each line of test cases .

The sample input

2
3 4
4102 642

Sample output

12
21262

  analysis ：

from g(x,m) Functions combined with recursion know the requirements m Time f(x),x and m The scope of is all up 10^9, Violence can't be . Take any number to simulate, and you will find that you will arrive at the end x=f(x)  The situation of , After that f(x) The value of no longer changes . When x=f(x) Time can be accumulated directly , Exit the cycle in time .

So why x=f(x) In the case? ？ Why not timeout in the worst case ？ Because every time I ask for f(x) I'll see you later (x+1) modulus , The result is equal to the x If so, it will be directly satisfied x=f(x) 了 , If you don't wait f(x) It must be less than x Of , That is to say f(x) The value of is constantly decreasing , And it is impossible to return to the previous value , in other words f(x) The value of will only decrease Until it's equal . It's easy to know x When it is a single digit f(x)=x, Let there be satisfaction in the middle f(x)=x Of x, for example 21,51,301…… The complexity is certainly enough .

Code ：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll x, m;
ll f(ll x)
{
    ll ans = 1;
    ll base = 1;
    while (x >= base)
    {
        base *= 10;
        ans = ans * (x % base); // Take out each number to be multiplied from the low order 
    }
    return ans % (x + 1); // return f(x)
}
void solve()
{
    cin >> x >> m;
    ll ans = 0;
    while (m--)
    {
        x = f(x);
        ans += x;
        if (x == f(x))
        {
            ans += m * x; // After that m Values of times are x
            cout << ans << "\n";
            return;
        }
    }
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}