企业官网建设流程全解析

原题来自：Romania OI 2002

求 AB 的所有约数之和 mod9901。

输入两个整数 A,B。

输出答案 mod 9901。

样例说明

2^3=8，8 的所有约数为 1,2,4,8，1+2+4+8=15,15 mod 9901=15，因此输出 15。

数据范围与提示：

对于全部数据，0≤A,B≤5×10^7。

1. 题意转换

这道题本质上是在求解数论中的“约数和公式”，并结合“唯一分解定理”、等比数列求和，最后利用费马小定理求乘法逆元来实现大数取模。这是一道极其经典的数论“缝合怪”。

2. 思考过程与解题思路

面对这道题，我们很容易陷入常规的模拟思维，但数据范围会立刻给出致命一击。

• 第一直觉的暴力解法与死穴：

  直觉上，我们会先算出A^B的值，然后用一个for循环从1到遍历找出所有约数并相加。

  但仔细看数据范围：。A^B 是一个宇宙大爆炸级别的数字，没有任何一种基础数据类型能存下它。就算用高精度，高达的遍历次数也必然会导致绝对的超时与mle。

• 推导正解的破局之路：

  既然不能把宏观的数字算出来，我们必须深入“基因层面”解决它。

  1. 降维（唯一分解定理）：把底数A拆解为质因数的乘积。那么 A^B只是把指数放大了B倍，质数种类没变：。

  2. 组装（约数和公式）：一个数的所有约数之和，等于它每个质因子的“等比数列求和”的乘积。即：。

  3. 提速（等比数列公式）：把括号里的等比数列化简，各项变为。

  4. 跨越除法（乘法逆元）：同余运算中除法不能直接取模。除以分母，等价于乘以它在模9901意义下的逆元。因为9901是质数，我们直接掏出费马小定理配合快速幂求解即可。

3. 算法设计与样例推演

• 核心算法：试除法分解质因数 + 快速幂求逆元。

• 核心状态转移方程式：

  对于A分解出的每一个质因子p，它在A^B中的总指数为c。它对总约数和的贡献因子为：

  Term =mod(9901)

  转换为逆元乘法公式：

  （mod 9901）

• 极简数据手玩推演（带入样例 A=2, B=3）：

  1. 分解A=2：底数p=2，在A中指数为1。

  2. 放大指数：在A^B中，总指数。

  3. 代入等比求和项公式：分子为。分母为。

  4. 计算逆元：1的逆元就是1。

  5. 汇总取模：。与样例输出完全一致。

4. 时空复杂度分析

• 时间复杂度：。

  最外层试除法寻找质因数的循环最多执行次（约7071次）。内部处理每个质因子时，快速幂的复杂度是对数级别的，质因子的种类k极小（不超过10个）。整体运算次数远在10^5以内，对于1s的时限来说耗时近乎为0 ms。

• 空间复杂度：。只使用了几个整型和long long变量来记录状态与累乘结果，没有开辟任何数组，完美避开空间超限陷阱。

5. 坑点与易错总结

这道题之所以杀伤力极大，是因为它集齐了数论工程代码里的四大暗雷：

1. 特判不可少：A=0时答案为0；B=0时 A^0 = 1，答案为1。

2. 逆元不存在的“黑洞”：费马小定理求逆元的前提是分母不能是模数9901的倍数。一旦，逆元直接失效。此时等比数列每一项对9901取模都是 1，共有 (c+1) 项，和直接等于。

3. C++ 负数取模未定义行为：计算分子取模时，极易算出负数。必须用黄金转正句型：(val % mod + mod) % mod。

4. 大质数扫尾防漏：for循环i * i <= a只能收割的质因数。根据数学定理，一个数最多只能包含一个大于的质因子。循环结束后，如果，必须对残留的这个唯一大质数执行相同的求和操作，其总指数必定是。

6. 标程详解

//唯一分解定理 等比数列求和公式 费马小定理求乘法逆元 #include <iostream> using namespace std; int a,b; const int mod=9901; long long sum;//存储最终的约数总和 //求快速幂取模 long long quickpow(long long a,int b){ long long ans=1; while(b>0){ if(b%2!=0){ ans=(ans*a)%mod; b--; } else{ a=(a*a)%mod; b/=2; } } return ans; } int main(){ cin>>a>>b; //特判a b均为0的情况 if(a==0){ cout<<0; return 0; } if(b==0){ cout<<1; return 0; } sum=1;//把下面for循环i=1的情况初始化进去 //找到a的所有质因数 for(int i=2;i*i<=a;i++){ int sumi=0;//记录原数字a中包含多少个质因子i //如果a%i==0 代表i是a的质因数 if(a%i==0){ //将该质因子除干净 并统计次数 while(a%i==0){ sumi++; a=a/i; } //当前质因子的底数 int p=i; //在a^b中 该质因子的总指数 int c=b*sumi; //接下来判断p-1是否为9901的倍数 //因为费马小定理求逆元要求p-1不能是9901的倍数 //如果是倍数，p这一项就不能用费马小定理去求 //当p-1是9901的倍数时 等比数列每一项取模后均为1 if((p-1)%mod==0){ //总共有c+1项 直接乘入答案并取模 sum=sum*(c+1)%mod; } //如果p-1不是9901的倍数 //就要用费马小定理配合快速幂求这一项 //的等比数列求和公式求出的和 else{ //先算分子部分 long long fz=(quickpow(p,c+1)-1+mod)%mod; //再计算分母部分 //分母部分根据费马小定理模质数p的意义下，整数a的逆元是a^(p-2) //直接求逆元 求完逆元就可以直接分子*分母然后求模了 long long fmu=(quickpow(p-1,mod-2)); sum=(sum*(fz*fmu)%mod)%mod; } } } //前面的for循环找质因数 可能会丢掉一个大于sqrt(a)的最大质因数 //且该大质数在a中的指数只能是1 在a^b中的指数即为b //所以我们要来判断一下 //如果最后的a不等于1 代表丢掉了一个质因数 if(a!=1){ //先判断对最后一个质因数p减掉1是否为9901的倍数 if((a-1)%9901==0){ //注意这里的项数是b+1 sum=sum*(b+1)%mod; } else{ //先算分子部分 long long fz=(quickpow(a,b+1)-1+mod)%mod; //再算分母部分 long long fmu=(quickpow(a-1,mod-2)); sum=(sum*(fz*fmu)%mod)%mod; } } cout<<sum; return 0; }