Loading...

洛谷P2613 [模板]有理数取余

check评论:0 条 remove_red_eye浏览量:398 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-24

我们要求$\frac{a}{b} \pmod p$的值,当然不能直接求

首先$p=19260817$,大家都知道这是一个质数,所以我们可以直接求一个数在他的模意义下的逆元

$\frac{a}{b}=a\times b^{-1} $,又因为$b^{p-1} \equiv 1\pmod p $,所以$b\times b^{p-2} \equiv 1 \pmod p$

所以直接输出$a\times b^{p-2}\pmod p$就行了qwq

#include <bits/stdc++.h>
using namespace std;
#define mod 19260817
long long a,b,ans;
void read(long long &x)
{
    int f=1;x=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(s=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10%mod+(ch-'0')%mod;
        ch=getchar();
    }
    x=x%mod*f;
}
long long ksm(long long x,long long p)
{
    long long res=1;
    for(;p;p>>=1,x=x*x%mod)
    {
        if(p&1)
        {
            res=res*x%mod;
        }
    }
    return res;
}
int main()
{
    read(a);
    read(b);
    if(b==0)
    {
        printf("Angry!");
        return 0;
    }
    ans=a*ksm(b,mod-2);
    printf("%lld",(ans%mod+mod)%mod);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名