题解 | #整除问题#

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

//计算大数加法
string bigAdd(string s1, string s2) {
    int s1Size = s1.size();
    int s2Size = s2.size();
    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());
    string res = "";
    int carrier = 0;
    if (s1Size > s2Size) {
        for (int i = 0; i < s2Size; i++) {
            int bitsum = (s1.at(i) - '0') + (s2.at(i) - '0') + carrier;
            if (bitsum >= 10) {
                bitsum -= 10;
                carrier = 1;
            } else {
                carrier = 0;
            }
            res += to_string(bitsum);
        }
        for (int i = s2Size; i < s1Size; i++) {
            int bitsum = (s1.at(i) - '0') + carrier;
            if (bitsum >= 10) {
                bitsum -= 10;
                carrier = 1;
            } else {
                carrier = 0;
            }
            res += to_string(bitsum);
        }
        if (carrier == 1) {
            res += "1";
        }
    } else if (s1Size == s2Size) {
        for (int i = 0; i < s1Size; i++) {
            int bitsum = (s1.at(i) - '0') + (s2.at(i) - '0') + carrier;
            if (bitsum >= 10) {
                bitsum -= 10;
                carrier = 1;
            } else {
                carrier = 0;
            }
            res += to_string(bitsum);
        }
        if (carrier == 1) {
            res += "1";
        }
    } else {
        for (int i = 0; i < s1Size; i++) {
            int bitsum = (s1.at(i) - '0') + (s2.at(i) - '0') + carrier;
            if (bitsum >= 10) {
                bitsum -= 10;
                carrier = 1;
            } else {
                carrier = 0;
            }
            res += to_string(bitsum);
        }
        for (int i = s1Size; i < s2Size; i++) {
            int bitsum = (s2.at(i) - '0') + carrier;
            if (bitsum >= 10) {
                bitsum -= 10;
                carrier = 1;
            } else {
                carrier = 0;
            }
            res += to_string(bitsum);
        }
        if (carrier == 1) {
            res += "1";
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

//计算大数乘法
string bigMulti(string basenum, int a) {
    string res = "0";
    string zerostr = "";
    reverse(basenum.begin(), basenum.end());
    while (a > 0) {
        int tmpa = a % 10;
        string tmpres="";
        int carrier = 0;
        for (int i = 0; i < basenum.size(); i++) {
            int multinum = (basenum.at(i) - '0') * tmpa + carrier;
            if (multinum >= 10) {
                carrier = multinum / 10;
                multinum = multinum % 10;
            } else {
                carrier = 0;
            }
            tmpres += to_string(multinum);
        }
        if (carrier != 0) {
            tmpres += to_string(carrier);
        }
        tmpres=zerostr+tmpres;
        reverse(tmpres.begin(), tmpres.end());
        res=bigAdd(tmpres,res);
        a=a/10;
        zerostr += "0";
    } 
    return res;
}

//计算大数除法 s1/s2
string bigDivide(string s1, string s2) {
    int lastnum=0;
    string res="";
    bool isExact=false;
    bool firstnozero=false;
    for(int i=0;i<s1.size();i++){
        int nownum=(s1.at(i)-'0')+lastnum;
        if(nownum/stoi(s2)==0){
            lastnum=nownum*10;
            if(firstnozero){
                res+="0";
            }
        }else{
            if(!firstnozero){
                firstnozero=true;
            }
            int nowbit=nownum/stoi(s2);
            res+=to_string(nowbit);
            lastnum=(nownum%stoi(s2))*10;
        }
        if(i==(s1.size()-1)){
            if(lastnum==0){
                isExact=true;
            }else{
                res="-1";//表示没有除尽
            }
        }
    }
    return res;
}

int main() {
    int n, a;
    while (cin >> n >> a) { // 注意 while 处理多个 case
        int kcounter = 0;
        string nown = "1";
        //注意这个地方要到n+1，因为写到n的时候还只是计算的(n-1)!
        for (int i = 1; i <= n+1; i++) {
            string nowdivires=bigDivide(nown, to_string(a));
            if (nowdivires!= "-1") {
                nown = nowdivires;
                kcounter++;
                nown = bigMulti(nowdivires, i);
            } else {
                nown = bigMulti(nown, i);
            }
        }
        cout<<kcounter<<endl;
    }
}
// 64 位输出请用 printf("%lld")

这可能是效率最低最笨的方式了，模拟了阶乘的计算，主要思想是：

1、使用大整数的加减乘除方法

2、在计算阶乘结果res1过程中对被除数a^k进行除法运算，如果能整除就把k++，res1变成除完以后的数，这样当完成阶乘运算时，得到的也是k的最大值