luogu P1593 因子和

不要吐槽博主总做这些数论氵题

首先我们看到这种因数问题,果断质因数分解

所以当前数\(a=p_1^{k_1}*p_2^{k_2}...*p_m^{k_m}\)

可得\(a^b=p_1^{k_1*b}*p_2^{k_2*b}...*p_m^{k_m*b}\)

考虑因数和,假设数\(a\)只有一个质因子\(p_1\),则因数和为\(\sum_{i=0}^{k_1}{p_1}^i\)

如果有第二个质因子\(p_2\)则因数和为\(\sum_{i=0}^{k_1}({p_1}^i*\sum_{j=0}^{k_2}{p_2}^j)=(\sum_{i=0}^{k_1}{p_1}^i)*(\sum_{j=0}^{k_2}{p_2}^j)\)

以此类推,我们要求的因数之和显然为\(\prod_{i=1}^m \sum_{j=0}^{k_i}{p_i}^j\)

至于后面那一段怎么求,先令\(f_i=\sum_{j=0}^{i}p^j\)

可以发现\(f_{i+1}=\sum_{j=0}^{i+1}p^j=p*(\sum_{j=0}^{i}p^j)+1=p*f_i+1\)

然后就可以偷税的使用矩乘了(如果不会请参考这题)

代码如下

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#define LL long long
#define il inline
#define re register

using namespace std;
const LL mod=9901;
il LL rd()
{
    re LL x=0,w=1;re char ch;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
struct mrtx
{
  LL a[2][2];
  mrtx(){memset(a,0,sizeof(a));}
}a,b;
il mrtx mlt(mrtx a,mrtx b)
{
  mrtx c;
  for(int i=0;i<=1;i++)
    for(int j=0;j<=1;j++)
      for(int k=0;k<=1;k++)
        c.a[i][j]=(c.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod;
  return c;
}
il mrtx ksm(mrtx a,mrtx b,LL bb)    //这里直接把转移矩阵乘到初始矩阵上去
{
  while(bb)
    {
      if(bb&1) a=mlt(a,b);
      b=mlt(b,b);
      bb>>=1;
    }
  return a;
}
LL p[20][2],tt,n,m,ans=1;

int main()
{
  n=rd(),m=rd();
  int srt=sqrt(n);
  for(int i=2;i<=srt;i++)
    {
      if(n%i!=0) continue;
      p[++tt][0]=i;
      while(n%i==0) ++p[tt][1],n/=i;
    }
  if(n>1) p[++tt][0]=n,p[tt][1]=1;
  a.a[0][0]=a.a[0][1]=1,b.a[1][0]=b.a[1][1]=1;
  for(int i=1;i<=tt;i++)
    {
      p[i][1]*=m;
      b.a[0][0]=p[i][0];
      ans=(ans*ksm(a,b,p[i][1]).a[0][0])%mod;
    }
  printf("%lld\n",ans);
  return 0;
}