约数之和
题目描述
假设现在有两个自然数A和B,S是A B的所有约数之和。
请你求出S mod 9901的值是多少。
输入格式
在一行中输入用空格隔开的两个整数A和B。
输出格式
输出一个整数,代表S mod 9901的值。
数据范围
0 ≤ A,B ≤ 5×10 ^ 7
输入样例:
2 3
输出样例:
15
注意: A和B不会同时为0。
题解:
公式推导:
第一步,质因数分解:由算术基本定理得任意一个数A = p1 ^ k1 * p2 ^ k2 * … * pn ^ kn。(其中p1-pn为A所有的质因数),则 A ^ B = p1 ^ k1*B * p2 ^ k2 * B * … * pn^kn * B。
第二步(补充),因子个数,设x为A的一个约数,则A必定可由若干个p1-pn相乘得到,对于任一个质因子pi,可为其他因子贡献的数量为从0到ki,共1+ki个。由乘法原理得,数A所有的因子个数为C = (k1+1) * (k2+1) * … * (kn + 1).
第三步,因子和,设Sn = (p1 ^ 0 + p1 ^ 1 + … + p1 ^ k1)* (p2 ^ 0 + p2 ^1 + … + p2 ^ k2)* … * (pn ^ 0 + pn ^ 1 + … + pn^kn),展开可得到C项,每一项都是A的因子。
第四步,公式推导,设sum(p,k) = p ^ 0 + p ^ 1 + … + p ^ k. 一共k+1项,我们对k分类讨论,k为奇数时,k+1为偶数,例如k = 7,sum(p,7) = (p ^ 0 + p ^ 1 + p ^ 2 + p ^ 3 ) + (p ^ 4 + p ^ 5 + p ^ 6 + p^7)
我们对其分成数量相等的两组式子,又p ^ 4 + p ^ 5 + p ^ 6 + p ^ 7 = p^4 * (p^0 + p^1 + p^2 + p^3 ),所以sum(p,7) = (p^0 + p^1 + p^2 + p^3 ) * (1 + p ^ 4).更一般的,sum(p,k) = (p ^ 0 + p ^ 1 + … + p^k/2 ) * (1 + p^(k/2+1) ) = sum(p,k/2) * (1 + p^(k/2+1) ) ,其中k为奇数.
k为偶数时,k+1为奇数,sum(p,k) = p ^ 0 + p ^ 1 + … + p^k = 1 + p * (p^0 + p ^1 + … + p^(k-1) ) = 1 + p * sum(p,k-1).
当然,最后需要注意的是,我们求A^B的约数和时,调用的sum(p,k),k应该是第一步推导的kB。并且k为奇数时,我们求幂可以使用快速幂算法。
代码如下:
#include<iostream>
#include<cstring>
using namespace std;
const int mod = 9901;
int kum(int a,int b) //快速幂
{
a %= mod;
int ans = 1;
while(b)
{
if(b&1)ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
int sum(int p, int k) //公式递推
{
if(k == 0) return 1;
if(k % 2 == 0)return (1 + p % mod * sum(p, k - 1)) % mod;
return (1 + kum(p, k/2 + 1)) * sum(p, k/2) % mod;
}
int main()
{
int a, b;
cin >> a >> b;
int res = 1;
for(int i = 2; i <=a; i++){
int s = 0;
while(a % i == 0){ //找出有几个质因数
s++;
a/=i;
}
if(s) res = res * sum(i, s * b) % mod;
}
if(!a)res = 0;
cout << res << endl;
return 0;
}
上一篇: 求排列的逆序数