Kaprekar Number

发布于 2023-03-01 | 分类于 oi | 3分钟 | 365字数 | 浏览量：

问题描述

定义函数 $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

样例输入2

10 3

样例输出2

#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;
}