POJ – 1845 – Sumdiv (逆元)

2018年2月22日 0 条评论 3 次阅读 0 人点赞

在学习文章逆元详解时做的一道例题

题目链接:POJ - 1845

题目大意:

给定两个正整数,求的所有因子和对9901取余后的值。

题目分析:

见原文

给出代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>
#include <cstdio>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int mod=9901;
const int maxn=10005;
int p[maxn];
bool prime[maxn];
int cnt=0;
void is_prime()
{
    memset(prime,true,sizeof(prime));
    for(int i=2; i<maxn; i++)
    {
        if(prime[i]==true)
        {
            p[cnt++]=i;
            for(int j=i*i; j<maxn; j=j+i)
                prime[j]=false;
        }
    }
}
LL multi(LL a,LL b,LL m)
{
    LL ans = 0;
    a %= m;
    while(b)
    {
        if(b & 1)
        {
            ans = (ans + a) % m;
            b--;
        }
        b >>= 1;
        a = (a + a) % m;
    }
    return ans;
}
LL pow_mod(LL a,LL b,LL m)
{
    LL ans=1;
    a%=m;
    while(b)
    {
        if(b & 1)
        {
            ans = multi(ans,a,m);
            b--;
        }
        b >>= 1;
        a = multi(a,a,m);
    }
    return ans;
}
LL solve(LL A,LL B)
{
    LL ans=1;
    for(int i=0; i<cnt; i++)
    {
        if(A%p[i]==0)
        {
            int ccnt=0;
            while(A%p[i]==0)
            {
                A=A/p[i];
                ccnt++;
            }
            LL M=(p[i]-1)*mod;
            LL temp=pow_mod(p[i],ccnt*B+1,M);
            temp=temp+M-1;
            temp=temp%M;
            temp=temp/(p[i]-1);
            ans*=temp;
            ans=ans%mod;
        }
    }
    if(A>1)
    {
        LL M=(A-1)*mod;
        LL temp=pow_mod(A,B+1,M);
        temp=temp+M-1;
        temp=temp%M;
        temp=temp/(A-1);
        ans*=temp;
        ans=ans%mod;
    }
    return ans;
}
int main()
{
    is_prime();
    LL A,B;
    while(cin>>A>>B)
    {
        LL ans=solve(A,B);
        cout<<ans<<endl;
    }
    return 0;
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)