poj 1845 Sumdiv

点击打开链接poj 1845

思路：数学+二分
分析：
1 题目要求的是A^B的所有因子的和对9901取模
2 先看几个数学定理

1：整数的唯一分解定理(如果A本身就是素数的话，那么本身就是分解式)
任意正整数都有且只有一种方式写出其素因子的乘积表达式。
A = (p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)   其中pi均为素数;
A^B = p1^(k1*B) * p2^(k2*B)*...* pn^(kn*B);
 
2：约数和公式
对于已经分解的整数A = (p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)
则A的所有因子之和为
sum = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)
则A^B的所有的因子之和为
sum = (1+p1+p1^2+...+p1^(a1*B)) *(1+p2+p2^2+...+p2^(a2*B)) *...*(1+pn+pn^2+...+pn^(an*B))

3：同余模公式
(a+b)%m=(a%m+b%m)%m
(a*b)%m=(a%m*b%m)%m
(a-b)%m=(a%m-b%m)%m

3 那么假设我们现在求出了A的分解式的pi和ki，那么现在要求的是约数的和，如果直接进行求解的话肯定是会溢出long long的，所以直接求这个思路是不行的。
我们现在来考虑这两个数组
1+p1+p2+p3+p4+p5+p6+p7 = (1+p1+p2+p3)+p4*(1+p1+p2+p3) = (1+p4)*(1+p1+p2+p3);
1+p1+p2+p3+p4+p5+p6 = (1+p1+p2)+p4*(1+p1+p2) + p3 = (1+p4)*(1+p1+p2) + p3;
那么推广到一般的n，就可以分成n是奇数和n是偶数的情况，然后利用上面的最右边的式子求ans。但是如果直接求是不行的，这个时候你可以仔细观察一下这个式子的一般式
如果n数奇数： (1+p^(n/2+1))*(1+p1+...+p^(n/2)); 如果n是偶数：(1+p^(n/2+1))*(1+p1+...+p^(n/2))+p^(n/2);
根据(1+p1+...+p^(n/2))，这个就是原式的一半，那么根据这个规律我们就可来利用递归每一次都进行二分求解即可。

4 注意取模的运用，像这一类的题目，数据量很大的都是要用long long。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long int64;
#define MAXN 100010
#define MOD 9901

int64 a , b , pos , ans;
int64 p[MAXN] , k[MAXN];

/*求出a的分解式的pi和ki*/
void prime(){
   pos = 0;
   for(int64 i = 2 ; i*i <= a ; i++){
      if(a%i == 0){
        p[pos] = i;
        k[pos] = 0;
        while(a%i == 0){
           k[pos]++;
           a /= i;
        }
        pos++;
      }
   }
   /*假设a本身就是一个素数*/
   if(a != 1){
     p[pos] = a;
     k[pos++] = 1;
   }
}

/*快速幂求次方*/
int64 Pow(int64 x , int64 y){
    int64 tmp = 1;
    while(y){
       if(y&1)
         tmp = (tmp%MOD)*(x%MOD)%MOD;
       y >>= 1;
       x = (x%MOD)*(x%MOD)%MOD;
    }
    return tmp;
}

/*二分求解等比数列的和1+x+x^2+x^3...+x^y*/
int64 sum(int64 x , int64 y){
    if(y == 0)
       return 1;
    /*是奇数*/
    if(y&1)
       return (sum(x , y/2)%MOD)*((1+Pow(x , y/2+1))%MOD)%MOD;
    /*是偶数*/
    else
       return ((((sum(x , y/2-1)%MOD)*((1+Pow(x , y/2+1))%MOD))%MOD) + (Pow(x , y/2)%MOD))%MOD;
}

int main(){
   while(scanf("%lld%lld" , &a , &b) != EOF){
      prime();
      /*求和*/
      ans = 1;
      for(int i = 0 ; i < pos ; i++)
         ans = (ans%MOD)*(sum(p[i] , k[i]*b)%MOD)%MOD;
      printf("%lld\n" , ans);
   }
   return 0;
}