洛谷P2613 【模板】有理数取余

@Pelom  October 12, 2021

题意

求$c=\frac{a}{b} \bmod 19260817$的值

数据范围:$0 \le a,b \le 10^{10001}$

题解

$$ \begin{aligned} \frac{a}{b} &= a \cdot b^{-1} \\ & \equiv (a \bmod p) \cdot (b^{-1} \bmod p) \end{aligned} $$

转化为$a \times b$的逆元
同时,由于输入过大,在快读时取模处理

代码:

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=19260817;
int a,b;
inline int read(){
    int res=0;
    char c=getchar();
    for(;c<'0' || c>'9';c=getchar());
    for(;c>='0' && c<='9';c=getchar())
        res=(res*10+c-'0')%mod;
    return res;
}
inline int Pow(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod;
    }
    return res;
}
int main(){
    a=read();
    b=read();
    if(b==0){
        puts("Angry!");
        return 0;
    }
    printf("%d",1ll*a*Pow(b,mod-2)%mod);
    return 0;
}

添加新评论