数位操作1

题号 NC205529
名称 数位操作1
来源 第十五届中北大学算法与程序设计竞赛（公开赛）

解题思路

对 n 分解因数，且每个因数都必须是个位数。
如果 n > 9，使用循环 for i=9 downto 2 作为因数，这样能使分解得到的因数最少；
当 n 可以整除，记录下 i 因数，n = n / i。
一直进行上述步骤，直到 n 是个位数时结束。
将记录下的因数从小到大排序，较小的数为高位，这样最后得到的 ans 是最小的。

还要注意 ans > 9，当 n < 10 时，分解因数 n = n * 1。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

long long func(long long n){
    if(n < 9){
        return (10 + n);
    }
    vector<int> nums;
    while(n > 9){
        bool flag = false;
        for(int i=9; i>=2; --i){
            if(n % i == 0){
                flag = true;
                nums.push_back(i);
                n /= i;
                break;
            }
        }
        if(!flag){
            return -1;
        }
    }
    nums.push_back(n);
    sort(nums.begin(), nums.end());
    long long ans = 0;
    for(int i=0; i<nums.size(); ++i){
        ans *= 10;
        ans += nums[i];
    }
    return ans;
}

int main(){
    long long n;
    while(cin >> n){
        cout << func(n) << endl;
    }
    return 0;
}