大数分解，整除概念

给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。
https://blog.csdn.net/csyifanZhang/article/details/105754286
↑更好的阅读体验

首先阶乘范围太大，不能直接longlong。所以我们要找到整除的真正含义：

首先，对于一个很大的数a，我们不能直接存储它的值，但是我们可以把它表示成质因数的积，于是第一步我们把a先转化成质因数

$\color{red}{大整数的质因数分解}$

核心代码只有几行，从小素数到大素数找起，一旦遇到一个素数因子就不断的将其从a中除掉。有了a的素数因子积的形式， $\mathbf{a=p_1^{x1}p_2^{x2}...p_n^{xn}}$ ，那么给a取k次方就变成了 $\mathbf{a=p_1^{k*x1}p_2^{k*x2}...p_n^{k*xn}}$

map<int, int> m, ma;
for (int i = 0; i < cnt&&primes[i] <= a; i++) {
    while (a%primes[i] == 0) {
        ma[primes[i]]++; a /= primes[i];
    }
}

此时如果我们能把n分解成 $\mathbf{n=p_1^{y1}p_2^{y2}...p_n^{yn}}$ ，那么整除就代表了a的所有素数因子n都有，而且在n中的因此的次幂必然比a中的次幂高，那么我们必须先将阶乘转化为质因数的组合 $\color{red}{阶乘的质因数分解}$

阶乘的分解与普通数字的分解不同，如果我们想知道 $n!$ 中有多少5的因子，那么我们从20开始

$20!=20*...*15*...*10*...*5*...*1=2432902008176640000$

显然有4个带5的因子，因此答案为4，我们只需要进行 $\color{blue}{N/5}$ 的运算就可以简单的算出他有几个带5的因子。但是我们显然有 $25*4=100，125*8=1000$ ，这些数字又应该如何进行统计？注意到 $25=5^2,125=5^3$ ，如果我们使用 $N/5$ 进行统计，那么25得到的结果只能是5，但是
$ $25=5*5*24*...*20*...*15*...*10*...*5*...*1=15511210043330985984000000$ $
所以对于所有25的倍数，我们==需要再进行一次统计==，当然对于所有125的倍数，我们又要==多进行一次统计==，总结一下就是

$sum=N/5+N/25+N/125+...+N/5^n|\frac{N}{5^n}>0$

注意这是一个逐渐推进的过程， $N/5$ 对所有5的倍数统计一次， $N/25$ 对所有25的倍数统计一次，以此类推。

$sum(51)=10+2$ $5的倍数：5,10,15,20,25,30,35,40,45,50;\;\;25的倍数：25,50$

完结撒花

        map<int, int> m, ma;
        //n！的质因子分解
        for (int i = 0; i < cnt && primes[i] <= n; i++) {
            ll t = n, base = primes[i];
            while (t / base > 0) {
                m[primes[i]] += t / base;
                base *= primes[i];
            }
        }

最后求出最大的k，使得 $a^k$ 可以被整除， $a^{k+1}$ 不能被整除，既然整除关系已经转化为了因此的幂次之间的关系，对于a的某个因子 $p_m^x$ 他的次数是x，他在n中的幂次假设为y，那么最多取y/x次方之后a的该因子就不小于n中该因子的次数了，即幂次再大就不能整除了。

        ll res = inf;
        for (map<int, int>::iterator i = ma.begin(); i != ma.end(); i++) {
            ll num = (*i).first, cnt = (*i).second;//a的第i个质因子的值和因子数目
            if (cnt > m[num]) { res = 0; break; }
            //k次方就是给每个因子数目cnt×k。
            //要保证整除，a^k的因子num数目最大等于m[num]
            //因此其最多增加 k<=m[num]/k
            res = min(m[num] / cnt, res);
        }

ll isPrime[MAX], primes[MAX], cnt;

int main() {
    ll n, a;
    fill(isPrime, isPrime + MAX, 1);
    //埃及筛法：筛取1-1000所有素数
    for (int i = 2; i < MAX; i++) {
        if (isPrime[i])
            for (int j = i * 2; j < MAX; j += i)
                isPrime[j] = 0;
    }
    for (int i = 2; i < MAX; i++)if (isPrime[i])primes[cnt++] = i;
    while (cin >> n >> a) {
        map<int, int> m, ma;
        //n！的质因子分解
        for (int i = 0; i < cnt && primes[i] <= n; i++) {
            ll t = n, base = primes[i];
            while (t / base > 0) {
                m[primes[i]] += t / base;
                base *= primes[i];
            }
        }

        //a的质因子分解与阶乘不同，每次找到一个因子就把他除掉
        for (int i = 0; i < cnt&&primes[i] <= a; i++) {
            while (a%primes[i] == 0) {
                ma[primes[i]]++; a /= primes[i];
            }
        }
        ll res = inf;
        for (map<int, int>::iterator i = ma.begin(); i != ma.end(); i++) {
            ll num = (*i).first, cnt = (*i).second;//a的第i个质因子的值和因子数目
            if (cnt > m[num]) { res = 0; break; }
            //k次方就是给每个因子数目cnt×k。
            //要保证整除，a^k的因子num数目最大等于m[num]
            //因此其最多增加 k<=m[num]/k
            res = min(m[num] / cnt, res);
        }
        cout << res << endl;
    }
}