洛谷P1593 因子和

题目描述

输入两个正整数a和b，求a^b的因子和。结果太大，只要输出它对9901的余数。

输入输出格式

输入格式：

仅一行，为两个正整数a和b(0≤a,b≤50000000)。

输出格式：

a^b的因子和对9901的余数。

输入输出样例

输入样例#1：

2 3

输出样例#1：

15
看似不可做，其实非常简单
任意正整数都有且只有一种方式写出其素因子的乘积表达式。
A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)
其中 pi 均为素数
那么A^B=(p1^(k1*B))*(p2^(k2*B))*(p3^(k3*B))*....*(pn^(kn*B))
显然ans=∑∑.....∑(p1^i1)*(p2^i2)*.....(pk^ik)
　　　=∑∑.....∑(pk^ik)

但是k*B最大可以达到30000×50000000(极限估算)
这里我们运用指数取模的方法，因为模数很小
根据费马小定理，我们证出：
a^x≡a^(x%μ(p)) (mod p)            μ(p)=9900，p=9901
这样我们发现，∑其实存在长度为μ(p)的循环节
这样，就算k*B再大，我们也可以通过O(μ(p))的求和处理算出循环节
然后就可以直接算出∑

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long lol;

 lol A,B,pri[],cnt[],ans,pw[],tot;

 int main()

 {lol x,i,j;

   cin>>A>>B;

   x=A;

   for (i=;i*i<=A;i++)

     {

       if (x%i==)

     {

       pri[++tot]=i;

       while (x%i==)

         {

           cnt[tot]++;

           x/=i;

         }

     }

     }

   if (x!=)

     {

       pri[++tot]=x;

       cnt[tot]=;

     }

   for (i=;i<=tot;i++)

     cnt[i]*=B;

   ans=;

   for (i=tot;i>=;i--)

     {

       pw[]=;

       lol s=,as=;

       for (j=;j<=&&j<=cnt[i];j++)

     {

       pw[j]=pw[j-]*pri[i]%;

       s=(s+pw[j])%;

       if (cnt[i]%==j)

         as=s;

     }

       ans=(ans*((cnt[i]/)*s+as)%)%;

     }

   cout<<ans;

 }