算法竞赛进阶指南-0x02-Sumdiv

2022-01-17 题解

这一题用到了两个数学上的结论，一是每一个正整数都可以分成若干个质因数的次幂相乘，通过乘法分配律可以再将次幂化为多项式相加，具体比较复杂，看书。

二是求质因数的一个方法——试除法。这一题需要用到原数的质因数。一般的思路是将原数范围内的所有质数求出来，再从这些质数中找原数的因数。但这一题原数非常大（5e7），用一般的筛都会超时。所以需要用到试除法。

试除法就是：从2开始枚举i，看原数是否能整除i，能整除的话就将i记录下来作为原数的一个质因数，并让原数一直除以i，直到整除不了为止。之后看除完i的剩下的这个原数是否能整除更大的i，直到i大于剩下的原数为止，具体看下面的代码。

需要注意一点：最后需要判断剩下的原数是否比1大，如果比1大的话，剩的这个数也是原数的一个质因数，要记录下来

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
const long long mod = 9901;
vector<pair<long long, long long> > p;
long long ksm(long long x, long long n)
{
    long long ret = 1;
    for (; n; n >>= 1)
    {
        if (n & 1)
            ret = ret * x % mod;
        x = x * x % mod;
    }
    return ret % mod;
}
long long count(long long x, long long n)
{
    if (!x)
        return 0;
    if (!n)
        return 1;
    if (n & 1)
        return count(x, n >> 1) * (ksm(x, (n >> 1) + 1) + 1) % mod;
    return ksm(x, n >> 1) + count(x, (n >> 1) - 1) * (ksm(x, (n >> 1) + 1) + 1) % mod;
}
int main()
{
    long long a, b, i, j, sum, res = 0;
    scanf("%lld%lld", &a, &b);
    
    for (i = 2; i * i <= a; i++)//试除法
    {
        if (a % i == 0)
        {
            sum = 0;
            while (a % i == 0)
            {
                sum++;
                a /= i;
            }
            if (sum)
                p.push_back(make_pair(i, sum));
        }
    }
    if (a > 1)
        p.push_back(make_pair(a, 1));//“记录下来”
    
    for (i = 0; i < p.size(); i++)
    {
        if (!res)
            res = 1;
        res *= count(p[i].first, p[i].second * b);
        res %= mod;
    }
    printf("%lld\n", res);
    return 0;
}