欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Acwing-97-约数之和(整数分解, 递推分治)

程序员文章站 2022-05-08 19:05:38
...

链接:

https://www.acwing.com/problem/content/99/

题意:

假设现在有两个自然数A和B,S是AB的所有约数之和。

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

思路:

考虑a^b次方的约数可以变为对a进行质数分解,对每个指数的次数乘上b.就构成了a^b的约数集合.
同时求和就是每个质数的组合.可以变成对每个质数求起0次到k次的和,将每个和相乘.
求0次到k次的和时可以用分治,将一个和分成两半来求.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 9901;

int a, b;

LL QuickPow(LL a, LL b)
{
    LL res = 1;
    while (b)
    {
        if (b&1)
            res = (res*a)%MOD;
        b >>= 1;
        a = (a*a)%MOD;
    }
    return res;
}

LL Sum(LL p, LL c)
{
    if (c == 0)
        return 1LL;
    if (c%2 == 0)
        return (((1LL+QuickPow(p, c/2)) * Sum(p, c/2-1))%MOD+QuickPow(p, c))%MOD;
    else
        return ((1LL+QuickPow(p, (c+1)/2))*Sum(p, c/2))%MOD;
}

int main()
{
//    cout << Sum(2, 3) << endl;
    scanf("%d%d", &a, &b);
    LL res = 1;
    for (int i = 2;i <= a;i++)
    {
        int cnt = 0;
        while (a%i == 0)
        {
            cnt++;
            a/=i;
        }
        if (cnt)
            res = res*Sum(i, cnt*b)%MOD;
    }
    if (a == 0)
        printf("0\n");
    else
        printf("%lld\n", res);

    return 0;
}