【题目描述】原题来自Romania OI 2002求 AB 的所有约数之和 mod9901。【输入】输入两个整数 A,B。【输出】输出答案 mod 9901。【输入样例】2 3【输出样例】15【提示】样例说明2^388 的所有约数为 1,2,4,8124815,15 mod 990115因此输出 15。数据范围与提示对于全部数据0≤A,B≤5×10^7。1. 题意转换这道题本质上是在求解数论中的“约数和公式”并结合“唯一分解定理”、等比数列求和最后利用费马小定理求乘法逆元来实现大数取模。这是一道极其经典的数论“缝合怪”。2. 思考过程与解题思路面对这道题我们很容易陷入常规的模拟思维但数据范围会立刻给出致命一击。第一直觉的暴力解法与死穴直觉上我们会先算出A^B的值然后用一个for循环从1到遍历找出所有约数并相加。但仔细看数据范围。A^B 是一个宇宙大爆炸级别的数字没有任何一种基础数据类型能存下它。就算用高精度高达的遍历次数也必然会导致绝对的超时与mle。推导正解的破局之路既然不能把宏观的数字算出来我们必须深入“基因层面”解决它。降维唯一分解定理把底数A拆解为质因数的乘积。那么 A^B只是把指数放大了B倍质数种类没变。组装约数和公式一个数的所有约数之和等于它每个质因子的“等比数列求和”的乘积。即。提速等比数列公式把括号里的等比数列化简各项变为。跨越除法乘法逆元同余运算中除法不能直接取模。除以分母等价于乘以它在模9901意义下的逆元。因为9901是质数我们直接掏出费马小定理配合快速幂求解即可。3. 算法设计与样例推演核心算法试除法分解质因数 快速幂求逆元。核心状态转移方程式对于A分解出的每一个质因子p它在A^B中的总指数为c。它对总约数和的贡献因子为Term mod(9901)转换为逆元乘法公式mod 9901极简数据手玩推演带入样例 A2, B3分解A2底数p2在A中指数为1。放大指数在A^B中总指数。代入等比求和项公式分子为。分母为。计算逆元1的逆元就是1。汇总取模。与样例输出完全一致。4. 时空复杂度分析时间复杂度。最外层试除法寻找质因数的循环最多执行次约7071次。内部处理每个质因子时快速幂的复杂度是对数级别的质因子的种类k极小不超过10个。整体运算次数远在10^5以内对于1s的时限来说耗时近乎为0 ms。空间复杂度。只使用了几个整型和long long变量来记录状态与累乘结果没有开辟任何数组完美避开空间超限陷阱。5. 坑点与易错总结这道题之所以杀伤力极大是因为它集齐了数论工程代码里的四大暗雷特判不可少A0时答案为0B0时 A^0 1答案为1。逆元不存在的“黑洞”费马小定理求逆元的前提是分母不能是模数9901的倍数。一旦逆元直接失效。此时等比数列每一项对9901取模都是 1共有 (c1) 项和直接等于。C 负数取模未定义行为计算分子取模时极易算出负数。必须用黄金转正句型(val % mod mod) % mod。大质数扫尾防漏for循环i * i a只能收割的质因数。根据数学定理一个数最多只能包含一个大于的质因子。循环结束后如果必须对残留的这个唯一大质数执行相同的求和操作其总指数必定是。6. 标程详解//唯一分解定理 等比数列求和公式 费马小定理求乘法逆元 #include iostream using namespace std; int a,b; const int mod9901; long long sum;//存储最终的约数总和 //求快速幂取模 long long quickpow(long long a,int b){ long long ans1; while(b0){ if(b%2!0){ ans(ans*a)%mod; b--; } else{ a(a*a)%mod; b/2; } } return ans; } int main(){ cinab; //特判a b均为0的情况 if(a0){ cout0; return 0; } if(b0){ cout1; return 0; } sum1;//把下面for循环i1的情况初始化进去 //找到a的所有质因数 for(int i2;i*ia;i){ int sumi0;//记录原数字a中包含多少个质因子i //如果a%i0 代表i是a的质因数 if(a%i0){ //将该质因子除干净 并统计次数 while(a%i0){ sumi; aa/i; } //当前质因子的底数 int pi; //在a^b中 该质因子的总指数 int cb*sumi; //接下来判断p-1是否为9901的倍数 //因为费马小定理求逆元要求p-1不能是9901的倍数 //如果是倍数p这一项就不能用费马小定理去求 //当p-1是9901的倍数时 等比数列每一项取模后均为1 if((p-1)%mod0){ //总共有c1项 直接乘入答案并取模 sumsum*(c1)%mod; } //如果p-1不是9901的倍数 //就要用费马小定理配合快速幂求这一项 //的等比数列求和公式求出的和 else{ //先算分子部分 long long fz(quickpow(p,c1)-1mod)%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)%99010){ //注意这里的项数是b1 sumsum*(b1)%mod; } else{ //先算分子部分 long long fz(quickpow(a,b1)-1mod)%mod; //再算分母部分 long long fmu(quickpow(a-1,mod-2)); sum(sum*(fz*fmu)%mod)%mod; } } coutsum; return 0; }