Kaprekar Number

问题描述

定义函数 $g_1(x),g_2(x),f(x),x>0$ 如下:

• $g_1(x)=$ 将 $x$ 的各位数字按照降序排序
• $g_2(x)=$ 将 $x$ 的各位数字按照升序排序，忽略前导零
• $f(x)=g_1(x)−g_2(x)$

例如，$g_1(318)=831$, $g_2(1024)=124$, $f(271)=721−127=594$。

给出整数 $N,K$, 定义数列 $a_0=N, a_{i+1}=f(a_i) (i≥0)$，求 $a_K$.

输入格式

输入一行包含两个整数 $N,K;N\le 10^9,K\le 10^5$。

输出格式

输出一个整数表示 $a_K$

样例输入1

1024 2

样例输出1

8172

样例输入2

10 3

样例输出2

0

#include <bits/stdc++.h>
using namespace std;

int g1(int n) {
    vector<int> v;
    while (n > 0) {
        v.push_back(n % 10);
        n /= 10;
    }
    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;
    for (auto i : v) {
        ans = ans * 10 + i;
    }
    return ans;
}

int g2(int n) {
    vector<int> v;
    while (n > 0) {
        v.push_back(n % 10);
        n /= 10;
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for (auto i : v) {
        ans = ans * 10 + i;
    }
    return ans;
}

int f(int n) {
    return g1(n) - g2(n);
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        n = f(n);
    }
    cout << n << endl;
    return 0;
}