问题 D: Sumdiv
时间限制: 1 Sec 内存限制: 128 MB
提交: 7 解决: 3
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]
题目链接：http://acm.ocrosoft.com/problem.php?cid=1703&pid=3
题目描述
求 
输入
输入两个整数 A,B
对于全部数据，0≤A,B≤5×107。
输出
输出答案mod 9901
样例输入
2 3 样例输出
15
思路：质因数分解加费马小定理降幂，具体见代码
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1000000
#define mod 9901
int m, p[maxn], c[maxn];
void divide(int n)//质因数分解
{
m = 0;
for (int i = 2; i*i <= n; i++)
{
if (n%i == 0)
{
p[++m] = i, c[m] = 0;
while (n%i == 0)n /= i, c[m]++;
}
}
if (n > 1)
p[++m] = n, c[m] = 1;//p存储y所含的质因数，c存储那个质因数的个数
}
ll quickpow(ll a, ll b, ll n)//快速幂
{
if (b == 0)return 1;//对b=0进行特判
if (b == 1)return a;
else
{
if (b % 2 == 0)
{
ll t = quickpow(a, b / 2, n);
return t * t%n;
}
else
{
ll t = quickpow(a, b / 2, n);
t = t * t%n;
t = t * a%n;
return t;
}
}
}
int main() {
int a, b;
cin >> a >> b;
divide(a);
for (int i = 1; i <= m; i++)
{
c[i] *= b;
}
ll result = 1;//记录因数和
//排列组合推出n的因数和计算公式（1+p1^1+p1^2+……+p1^c[p1]）*（1+p2^1+p2^2+……+p2^c[p2]）*……*（1+pm^1+pm^2+……+pm^c[pm]）
for (int i = 1; i <= m; i++)
{
//计算1+px^1+px^2+……+px^c[px]
ll xx = 0;
//把因数的幂的大小分成2种情况去计算，因为有mod 9901，所以9900个幂一次循环，当c[i]大于等于9899每9900个用费马小定理进行降幂 a^(p-1)≡1(mod p),
if (c[i] >= 9899)
{
for (int j = 0; j <= 9899; j++)
{
xx = (xx%mod + quickpow(p[i], j, mod)) % mod;
}
xx = (xx%mod * (c[i] / 9900) % mod) % mod;//循环几次乘一乘
for (int j = 0; j <= c[i] % 9900; j++)//多出来的单独去计算
{
xx = (xx%mod + quickpow(p[i], j, mod)) % mod;
}
}
else
{
for (int j = 0; j <= c[i]; j++)
{
xx = (xx%mod + quickpow(p[i], j, mod)) % mod;
}
}
result = (result%mod*xx%mod) % mod;
}
cout << result << endl;
}
京公网安备 11010502036488号