博客园阅读通道

前言

失恋了跑过来写这题，想当年这题咕了好久，现在分分钟切了。

ACwing题目地址

Solution

通过唯一分解定理：

$$A=p_1^{\alpha_1}*p_2^{\alpha_2}…p_n^{\alpha_n}$$

所以：

$$A^B=p_1^{\alpha_1B}*p_2^{\alpha_2B}…p_n^{\alpha_nB}$$

通过自己研究研究可以知道的两个定理：

• 1.约数个数定理：

$$Num(A)=(1+\alpha_1)*(1+\alpha_2)…(1+\alpha_n)$$

解释：从每一个质数里面任选一个次幂（选择范围 $[0,\alpha_i]$），与其他质数相组合就是一个约数，所以约数个数就是上面这个式子。

• 2.约数和定理：

$$Sum(A)=(1+p_1^1+p_1^2+…+p_1^{\alpha_1})*(1+p_2^1+p_2^2+…+p_2^{\alpha_2})…(1+p_n^1+p_n^2+…+p_n^{\alpha_n})$$

解释：每个括号里面就是每一个质数的任一个次幂（次幂范围 $[0,\alpha_i]$）之和，如果把括号拆开，就是每个括号里面选一个数乘起来，再把所有选择加起来。每个括号选一个数乘起来，不正对应每一个约数的值吗？所以约数和就是上面这个式子。

上面这个式子有 亿点点 难看，我们把它写简洁一点就是：

$$Sum(A)=\prod_{i=1}^n (\sum_{j=0}^{\alpha_i}p_i^j)$$

回到题目，在这个题目里的 约数和 就是如下式子：

$$Ans=\prod_{i=1}^n (\sum_{j=0}^{\alpha_i*B}p_i^j)$$

暴力计算复杂度 $O(n^2)$，还要带上个质因数分解的复杂度。本题数据 $n<=5*10^7$，因此要想办法优化。

发现 $\sum_{j=0}^{\alpha_i*B}p_i^j$ 不就是一个 等比数列求和 吗？ 等比数列求和公式

注意在 模意义 下，除一个数要用乘它的逆元代替，模数 $9901$ 是一个素数，可以用 费马小定理 直接求得逆元。 （这题目要用的东西还挺多的）

所以最后分别求出 $n$ 个等比数列求和，全部乘起来就是答案。每个等比数列 $a_0=1,q=p_i$ （$q$ 是公比）。这样我们就可以求出整个题目的解了。

求一次乘法逆元的复杂度是 $O(\log MOD)$，因为 $MOD$ 较小，可以忽略记为常数；求一次快速幂的复杂度是 $O(\log N)$ 这个应该小于 $32$。所以总复杂度应该是 $O(9 * \log n)$ (大雾 （有一个著名的定理 $n<=10^9$ 分解出来的质数不超过9个）

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define MOD 9901
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int A,B;
vector<pair<int,int> > p;
int Pow(int x,int y) {  //9901是质数，直接上费马小 
    int res = 1, base = x;
    while(y) {
        if(y&1) res = (res*base)%MOD; base = (base*base)%MOD; y >>= 1;
    }
    return res;
}
signed main()
{
    A = read(), B = read();
    if(A == 0) {
        puts("0"); return 0;
    }
    while(A > 1) {
        for(int i=2;i<=A;++i) {
            if(A%i == 0) {
                int num = 0;
                while(A%i == 0) A /= i, ++num;
                p.push_back(make_pair(i,num));
                break;
            }
        }
    }
    int ans = 1, inv, S;
    for(int i=0;i<p.size();++i) {
        inv = Pow(p[i].first-1+MOD%MOD,MOD-2);
        S = (Pow(p[i].first, p[i].second*B+1)-1+MOD)%MOD;
        S = (S*inv)%MOD;
        ans = (ans*S)%MOD;
    }
    printf("%lld\n",ans);
    return 0;
}

Summary

水题一道，只是做来安慰安慰自己的心情，使得自己能坚定地在OI路上走下去。

自己选择的路，跪着也要走完。朋友们，虽然这个世界日益浮躁起来，只要能够为了当时纯粹的梦想和感动坚持努力下去，不管其它人怎么样，我们也能够保持自己的本色走下去。 ——陈立杰