Vijos 1024 — 卡布列克圆舞曲

描述

卡布列克是一位数学家，他在研究数字时发现：任意一个不是用完全相同数字组成的四位数，如果对它们的每位数字重新排序，组成一个较大的数和一个较小的数，然后用较大数减去较小数，差不够四位数时补零，类推下去，最后将变成一个固定的数：6174，这就是卡布列克常数。

例如：4321-1234=3087
8730-378=8352
8532-2358=6174
7641-1467=6174
如果K位数也照此办理，它们不是变成一个数，而是在几个数字之间形成循环，称作卡布列克圆舞曲。例如对于五位数54321：
54321-12345=41976
97641-14679=82962
98622-22689=75933
97533-33579=63954
96543-34569=61974
97641-14679=82962
我们把82962 75933 63954 61974称作循环节，即卡布列克圆舞曲。

题目链接

https://vijos.org/p/1024

输入格式

文件包含若干行，每行为一个待求“卡布列克圆舞曲”的起始整数（小于maxlongint）

输出格式

每行为对应整数的循环节，数据之间用空格隔开。

样例输入

4321
54321

样例输出

6174
82962 75933 63954 61974

题目分析

将每次计算的结果按顺序存起来。每次运算的结果要先判断一下是否已经存在这个数，如果存在，说明循环节已经找到了，输出循环节即可；如果不存在，将运算结果保存，继续下一次运算。
值得注意的是，最初的这个数也要先存起来才行。

AC代码

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

int f(long long num) //寻找位置
{
    for (int i = 0; i < v.size(); i++)
    {
        if (num == v[i])
            return i;
    }
    return -1;
}

long long s_ll(string s)
{
    long long num = 0;
    for (int i = 0; i < s.length(); i++)
        num = num * 10 + s[i] - '0';
    return num;
}

int main()
{
    long long num, maxnum, minnum;
    char s[30];
    int index;
    string ss;
    while (cin >> num)
    {
        v.clear();
        v.push_back(num); //输入的这个数字也要放进去
        while (1)
        {
            sprintf(s, "%lld", num);
            ss = string(s);
            sort(ss.begin(), ss.end()); //最小数
            minnum = s_ll(ss);
            reverse(ss.begin(), ss.end()); //反转成最大数
            maxnum = s_ll(ss);
            num = maxnum - minnum;
            if ((index = f(num)) != -1)
                break;
            v.push_back(num);
        }
        for (int i = index; i < v.size(); i++)
        {
            if (i == v.size() - 1)
                printf("%lld\n", v[i]);
            else
                printf("%lld ", v[i]);
        }
    }
    return 0;
}