算法竞赛进阶指南：0x02递推与递归：分治：Sumdiv

题目位置&＃xff1a;https://www.acwing.com/problem/content/99/

借鉴&＃xff1a;https://www.acwing.com/solution/content/30343/

题目&＃xff1a;假设现在有两个自然数 A 和 B&＃xff0c;S 是的所有约数之和。请你求出 S mod 9901的值是多少。

#include
#include
using namespace std;
typedef long long LL;const int mod&＃61;9901;
int a,b;unordered_mapprimes;//快速幂
int poww(int x,int y)
{int ans&＃61;1;while(y){if(y&1)ans&＃61;(LL)ans*x%mod;y>>&＃61;1;x&＃61;(LL)x*x%mod;}return ans;
}//分解质因子
void divide(int n)
{for(int i&＃61;2; i<&＃61;n/i; i&＃43;&＃43;)if(n%i&＃61;&＃61;0)while(n%i&＃61;&＃61;0){n/&＃61;i;primes[i]&＃43;&＃43;;}if(n>1)primes[n]&＃43;&＃43;;
}//核心
int sum(int p,int c)
{if(c&＃61;&＃61;0)return 1;//递归结束条件 if(c%2)return (LL)(1&＃43; poww(p, (c&＃43;1)/2 ) ) * sum(p , (c-1)/2 )%mod;elsereturn ((LL)(1 &＃43; poww(p, c/2 ) )*sum(p,c/2-1) &＃43; poww(p,c) )%mod;
}int main()
{cin>>a>>b;divide(a);int ans&＃61;1;for(auto it:primes){int p&＃61;it.first,c&＃61;it.second*b;ans&＃61;(LL)ans*sum(p,c)%mod;}if(a&＃61;&＃61;0)ans&＃61;0;cout<}