AcWing 97.约数之和

假设现在有两个自然数A和B，S是

请你求出S mod 9901的值是多少。

输入格式

在一行中输入用空格隔开的两个整数A和B。

输出格式

输出一个整数，代表S mod 9901的值。

数据范围

输入样例：

输出样例：

注意: A和B不会同时为0。

【思路】：这是个数学题啊，一开始我的想法是唯一分解出最小的，然后标记存在几次方，然后暴力枚举

　　　　　这样是铁定超时的，那么我们要怎么实现这个题目呢？其实是因为我缺乏数学知识，那么我们

　　　　　假设唯一分解后的因子集合为{a, b, c} ^ b（这个代表b次方）,b == 1;

　　　　　那么约数的和sum = 1 + a + b + c + a * b + a * c + b * c + a * b * c

　　　　　可以看出sum = (1 + a) * (1 + b) * (1 + c)

　　　　　推广后可得sum = (1 + p1 + p1 ^ 2 + ....... + p1 ^ c1) * ...* (1 + pm + .... + pm ^ cm)这里指的是

　　　　　n方

　　　　　可得这就是一个等比数列求和

　　　　　Sn = (1 - q ^ n) / (1 - q)

　　　　　那么涉及两种做法

　　　　　就是等比数列的答案如何求？

　　　　　1，使用分治递归的想法去求解

　　　　　　当n是偶数的时候，sum(p, c) = 1 + p + p ^ 2 + p ^ 3 + ..... + p ^ n

　　　　　　举个例子

　　　　　　1 + p + p2 + p3 + p4 + p5 + p6 + p7 + p8

　　　　　　(1 + p + p2 + p3) + (p4 + p5 + p6 + p7) + p8

　　　　　　sum(p, c/2) + p(c / 2)sum(p, c/2) + pc

　　　　　　(1 + p(c / 2))sum(p, c / 2) + pc

　　　　　　当n是奇数的时候，

　　　　　　举个例子

　　　　　　1 + p + p2 + p3 + p4 + p5

　　　　　　(1 + p + p2) + (p3 + p4 + p5)

　　　　　　(1 + p + p2) + p3(1 + p + p2)

　　　　　　(1 + p(c + 1 / 2)) * sum(p, c - 1 / 2)

因为求和所以肯定是符合的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = 9901;
typedef long long ll;
/**
 等比数列求和公式：
 (- q ^ n + 1) / (1 - q)
 quick_pow
 质因数分解 + 唯一分解 + 约数求和
 
 **/
ll quick_pow(ll a, ll b)
{
    ll ans = 1;
    a %= MOD;
    while(b)
    {
        if(b & 1)
        {
            ans = ans % MOD * a;
        }
        a = a % MOD * a % MOD;
        b >>= 1;
    }
    return ans;
}
ll sum(ll p, ll c)
{
    if (c == 0)
        return 1;
    if(c & 1)
        return ((1 + quick_pow(p,(c + 1) >> 1)) * sum(p,(c - 1) >> 1)) % MOD;
    else
        return ((1 + quick_pow(p,c >> 1)) * sum(p,(c >> 1) - 1) + quick_pow(p,c)) % MOD;
}
int a, b;
int main()
{
    scanf("%d%d", &a, &b);
    ll sj = a;
    ll ans = 1;
    for(ll i = 2; i * i <= a + 1; i ++)
    {
        ll s = 0;
        while(a % i == 0)
        {
            s ++;
            a /= i;
        }
        //printf("%lld %lld
", i, s);
        ans = ans * sum(i, s * b) % MOD;
        //printf("ans = %lld
", ans);
    }
    if(a > 1)
        ans = ans * sum(a, b) % MOD;
    if(a == 0)
        printf("0
");
    else
    {
        printf("%lld
", ans);
    }
    return 0;
}