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

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

所以当前数\(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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include