颓了一个暑假我终于腆着脸回来更博客了 有没有R6带我飞的dalao啊

带模的减法一定要加上模数再取一遍模…

懵逼的 题目

传送至poj

扯淡的 题解

我们惊奇的发现 $A^B$的约数和就是

$$
(p_1^0 + p_1^1 + \cdots + p_1^{k_1\cdot B}) \cdot (p_2^0 + p_2^1 + \cdots +p_2^{k_2\cdot B}) \cdot (p_3^0 + p_3^1 + \cdots + p_3 ^{k_3 \cdot B}) \cdot (\cdots)
$$
的展开, 是不是很神奇?

那么我们只需要对每一个$p$求出$(p^0 + p^1 + \cdots + p^{k \cdot B})$就可以了

我们又发现, 这个式子其实就是个等比数列求和, 直接套分治板子就行了

然后就因为带模减法减成负数调了一下午… = =

沙茶的 代码

调了好久…肥肠的丑…

对了 千万别忘了是多组数据….

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define INF (50000000 + 5)
#define MAXN (4000000 + 5)
#define Aufun (9901)
#define LL long long
#define pii pair<int, int>
using namespace std;
LL a;
int b;
LL fp(LL pa, int pb)
{
    if (pb == 0)
        return 1;
    LL re = fp(pa, pb >> 1);
    re = (re * re) % Aufun;
    if (pb & 1)
        re = (re * pa) % Aufun;
    return re;
}
LL sum(LL p, int c)
{
    if (c == 1)
        return (p + 1) % Aufun;
    if (c == 0)
        return 1;
    LL re = sum(p, c >> 1);
    if (c & 1)
        return (re * (1ll + fp(p, (c + 1) >> 1ll))) % Aufun;
    else
        return (re * (1ll + fp(p, (c >> 1) + 1)) - fp(p, c + 1) + Aufun) % Aufun; 
}
int main()
{
    freopen("in.in", "r", stdin);
    freopen("WA.out", "w", stdout);
    while (scanf("%lld%d", &a, &b) == 2)
    {
        LL ans = 1;
        for (int i = 2; i <= sqrt((double)a) + 1; i++)
        {
            int dq = 0;
            while (a % i == 0)
                a /= i, ++dq;
            ans = (ans * sum((LL)i, dq * b)) % Aufun;
        }
        if (a > 1)
            ans = (ans * sum(a, b)) % Aufun;
        printf("%lld\n", ans);
    }
    return 0;
}

By 粉Bandit的彩虹六号萌新 Cansult

Bandit抬头看我的样子真的好帅啊嘤嘤嘤