POJ 1845-Sumdiv 题解（数论，约数和公式，逆元，高中数学）

题目描述

给定A,B，求A^B的所有因数的和，再MOD 9901

输入

一行两个整数 A 和 B。

输出

一行，一个整数

样例输入

2 3

样例输出

提示

对于100%的数据满足：0 <= A,B <= 50000000

这道题首先要想到有一个因数和公式

f[a] = ( 1 + p1 + p1^2 + .... + p1^q1 ) * ( 1 + p2 + p2^2 + .... + p2^q2 ) * ...... * ( 1 + pn + pn^2 +.....+ pn^qn )

由此我们知道，这道题需要分解质因数（唯一分解定理？？？

A^B可以直接分A，每个分出数的指数再×B就行（这应该都会

所以我们可以先打个素数表..

因为a，b都在50000000，计算器一算7000多的表就够了..

我们再观察因数和公式，如果一个一个求救太麻烦了，我们就发现了这是等比数列啊！！！

等比数列公式相信大家都会...

因为除数可能为负数，所以式子要上下都×-1整理一下

但这又有可能出现不是整数的情况，我们就需要用乘法逆元了（当时我卡在这了

这里先贴一个写的挺好的乘法逆元

inline long long extend_gcd(long long a,long long b,long long &x,long long &y)

{

    if(a==&&b==)

        return -1ll;

    if(b==)

    {

        x=1ll;

        y=0ll;

        return a;

    }

    long long d=extend_gcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

inline long long mod_reverse(long long a,long long n)

{

    long long x,y,d=extend_gcd(a,n,x,y);

    if(d==)

        return (x%n+n)%n;

    else

        return -1ll;

}

快速幂和乘法取模就不说了

下面贴代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define ll long long

ll vis[]={};

ll ys[]={},zs[]={};

ll vis1[]={};

ll ac[]={};

using namespace std;

ll n;

ll qmod(ll i,ll j)

{

    ll ans=;

    while(j)

    {

        if(j&)

        {

            ans*=i;

            ans%=;

        }

        i=i*i%;

        j>>=;

    }

    return ans%;

}

void prime()

{

    ll i,j,k=;

    for(i=;i<=;i++)

    {

        vis[i]=i;

    }

    i=;

    while(i*i<=)

    {

        if(vis[i]!=)

        {

            j=i<<;

            while(j<=)

            {

                if(vis[j]!=)

                {

                    k++;

                }

                vis[j]=;

                j=j+i;

            }

        }

        i++;

    }

}

int main()

{

    ll k=;

    ll i,j;

    ll A,b;

    ll a,n;

    cin>>a>>b;

    A=a;

    n=sqrt(a);

    prime();

    for(i=;i<=n;i++)

    {

        while((vis[i]!=)&&(a%vis[i]==))

        {

            vis1[i]=;

            ys[k]=vis[i]%;

            zs[k]++;

            a=a/vis[i];

        }

        if(vis1[i]==)

        {

            k++;

        }

    }

    k--;

    ll step=;

    ll re=,cf=;

    if(a!=&&a!=A)

    {

        ys[k+]=a%;

        zs[k+]=;

        step=;

    }

    else

    if(a==A)

    {

        ys[]=a%;

        zs[]=;

        k=;

    }

    if(step==)

    {

        k++;

    }

    ll count=;

    for(i=;i<=k;i++)

    {

        if(zs[i]!=)

        {

            zs[i]=zs[i]*b;

            count++;

        }

    }

    for(i=;i<=count;i++)

    {

        ll a1=qmod(ys[i]%,zs[i]+);

        a1=a1-;

        ll temp=(ys[i]-)%;

        ll a2=qmod(temp,);

        ac[i]=((a1%)*(a2%))%;

    }

    ll sum=ac[];

    for(i=;i<=count;i++)

    {

        sum=((sum%)*(ac[i]%))%;

    }

    cout<<sum;

}

巴特西

POJ 1845-Sumdiv 题解（数论，约数和公式，逆元，高中数学）

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章