【POJ 1845】 Sumdiv

用的东西挺全 最主要通过这个题学了约数和公式跟二分求等比数列前n项和 另一种小优化的整数拆分

 整数的唯一分解定理：

随意正整数都有且仅仅有一种方式写出其素因子的乘积表达式。

A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)   当中pi均为素数

约数和公式：

对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)

有A的全部因子之和为

S = (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)

用递归二分求等比数列1+pi+pi^2+pi^3+...+pi^n：

（1）若n为奇数,一共同拥有偶数项，则：

      1 + p + p^2 + p^3 +...+ p^n

= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))

      = (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))
->奇数时两边平分

上式红色加粗的前半部分恰好就是原式的一半，那么仅仅须要不断递归二分求和就能够了。后半部分为幂次式。将在以下第4点讲述计算方法。

（2）若n为偶数,一共同拥有奇数项,则:

      1 + p + p^2 + p^3 +...+ p^n

= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2)

      = (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);
->偶数时以n/2为中点二分 中点n/2需额外加上

上式红色加粗的前半部分恰好就是原式的一半，依旧递归求解

知道以上三点就好办了,代码量如开挂般少。。。(注意上long long 乘中会爆

代码例如以下:

#include <iostream>

#include <cstdio>

#include <cstring>

#define mod 9901

#define ll long long

using namespace std;

ll pow(ll a,ll b)//高速幂

{

    ll ans = 1;

    while(b)

    {

        if(b&1) ans = ans*a%mod;

        a = a*a%mod;

        b >>= 1;

    }

    return ans;

}

ll sum(ll p,ll k)//二分求等比数列前n项和

{

    if(!k) return 1;

    if(k&1) return sum(p,k/2)*(1+pow(p,k/2+1))%mod;

    else return (sum(p,k/2-1)*(1+pow(p,k/2+1))+pow(p,k/2))%mod;

}

ll make(ll a,ll b)//处理a的分解+答案

{

    int i;

    ll cnt,ans = 1;

    for(i = 2; i*i <= a; )//根号法+奇偶法

    {

        cnt = 0;

        while(a%i == 0)

        {

            a /= i;

            cnt++;

        }

        if(cnt) ans = ans*sum(i,b*cnt)%mod;

        if(i == 2) i++;//简单的奇偶优化

        else i += 2;

    }

    if(a != 1) ans = ans*sum(a,b)%mod;

    return ans;

}

int main()

{

    ll a,b;

    scanf("%lld %lld",&a,&b);

    printf("%lld\n",make(a,b));

    return 0;

}