问题 D: Sumdiv

时间限制: 1 Sec 内存限制: 128 MB
提交: 7 解决: 3
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1703&pid=3

题目描述

求的所有约数之和mod 9901

输入

输入两个整数 A,B

对于全部数据，0≤A,B≤5×107。

输出

输出答案mod 9901

样例输入

2 3

样例输出

思路：质因数分解加费马小定理降幂，具体见代码

代码：

#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;

}