题解 | #大整数的因子#

#include<iostream>
#include<string>
//大整数减法
std::string Substract(std::string s1, std::string s2)
{
    std::string result;
    int carry = 0;
    int i = s1.length()-1;
    int j = s2.length()-1;

    while(i >= 0 || j >= 0 || carry)//从后往前遍历，依次对应相减
    {
        int x = i >= 0 ? s1[i--] - '0' : 0;//位数不够就赋值为0
        int y = j >= 0 ? s2[j--] - '0' : 0;
        int diff = x - y - carry;
        if(diff < 0)//这里运用了补码的思想，如果小于0说明不够减，加上10为正确结果，同时进位变为1
        {
            diff += 10;
            carry = 1;
        }else{
            carry = 0;//够减则进位为0
        }
        //将相减的结果从头不断加入字符串
        result = std::to_string(diff) + result;
    }
    //移除数字前面的0
    while (result.length() > 1 && result[0] == '0')
    {
        result = result.substr(1);
    }
    return result;
}

//大整数除法
bool divide(std::string dividend, std::string divisor)
{
    std::string quotient;
    std::string reminder = "";
    for(char digit : dividend)
    {
        reminder += digit;//先找到大于除数的部分
        int count = 0;
        while(std::stoi(reminder) >= std::stoi(divisor))
        {
            //除法本质上就是减法，不断相减，直到小于除数
            reminder = Substract(reminder, divisor);
            count++;//每减一次该位的商就加1
        }
        quotient.push_back(count + '0');
    }

    while (quotient.length() > 1 && quotient[0] == '0')
    {
        quotient = quotient.substr(1);
    }
    // if(quotient.empty())
    // {
    //     return "0";
    // }
    while (reminder.length() > 1 && reminder[0] == '0')
    {
        reminder = reminder.substr(1);
    }
    if(reminder == "0" )
    {
        return true;
    }else{
        return false;
    }
}

int main()
{
    std::string s;
    while(std::cin >> s)
    {
        if(s == "-1") break;
        std::string result = "";
        for(int i = 2;i <= 9;i++)
        {
            if(divide(s, std::to_string(i)))
            {
                result = result + std::to_string(i) + " ";
            }
        }
        if(result.empty())
        {
            result = "none";
        }else{
            result.erase(result.length() - 1);
        }
        std::cout << result << std::endl;
    }
}