[POJ1845] Sumdiv

恶灬心 · 2019-05-25 20:11:57 · 个人记录

数论的公式

这题就是一道数论题。

1. 快速幂

一提到A^B，绝对绕不开快速幂。

long long Km(long long a,long long b,long long p)
{
    a%=P;
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

原理简介： 将B转化为2进制后发现。只有有1的位置我们才要将答案乘a的k次方。

2.整数分解

A=（k1^n1 k2^n2 ……）其中kn是一个质数且是A的一个约数nn是他的个数。

3.等比数列求和

这个就不太理解了。。 明明有S=（1-q^n）/(1-q）的，但是推了几个不对。。目测是快速幂后再减1时出现的问题。

<后记> 如果直接用公式就会出现失精的情况！ 切记。

题解解法：

（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))

上式的前半部分恰好就是原式的一半，那么只需要不断递归二分求和就可以了，后半部分为幂次式，快速幂即可。

（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);

完整代码。

#include <bits/stdc++.h>
using namespace std;
const long long P = 9901;
long long Km(long long a,long long b,long long p)
{
    a%=P;
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

long long ZC(long long a,long long b)  //等比数列求和，递归法；
{
    if(b==0) return 1;
    long long sum=1;
    if(b&1) return ((Km(a,b/2+1,P)+1)*ZC(a,b/2))%9901;   //公式；
    return ((Km(a,b/2+1,P)+1)*ZC(a,b/2-1)+Km(a,b/2,P))%9901;
}

long long S=1;
int main()
{
    long long A,B;
    cin>>A>>B;
    for(int i=2;i<=sqrt(A);i++)
    {
        int kn=0;
        while(A%i==0)
        {
            kn++;
            A/=i;
        }
        S=(S*ZC(i,kn*B))%P;
    }
    if(A>1) S=(S*ZC(A,B)%P)%P;
    cout<<S;
}