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

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

P2613 【模板】有理数取余

读入优化预处理

$\frac {a}{b}\mod 19620817$

也就是$a\times b^{-1}$

$a\times b^{-1}\mod 19620817=a\times b^{19620815}\mod 19620817$

除法转化为了乘法，同余的性质。。。

求一个逆元即可，根据费马小定理，由于$19620817$是一个质数

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const LL mod=;

void in(LL &x){

    char c=getchar();x=;int f=;

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'',x%=mod;

    x*=f;

}

LL a,b;

LL pow(LL x,LL y){

    LL s=;

    for(;y;y>>=,x=x*x%mod)

        if(y&) s=s*x%mod;

    return s;

}

int main()

{

    in(a),in(b);

    if(!b) printf("Angry!");

    else printf("%lld\n",a*pow(b,mod-)%mod);

    return ;

}