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

题目链接：P2613 【模板】有理数取余

题意：给出 $c=\frac{a}{b}$ ，求 $\frac{a}{b} \bmod 19260817$

$0 \le a \le 10^{10001},1\le b \le 10^{10001}$

令 $m=19260817$

注意这里模意义下的有理数其实就是

$$\frac{a}{b} \pmod m = ab^{-1} \pmod m$$

简单推推柿子吧

显然有

$$bc \equiv a \pmod{m}$$

令

$$b_0=b \bmod m,a_0 = a \bmod m$$

当 $b_0 \ne 0$ 即 $m \nmid b$ 时，有

$$c \equiv a_0 b_0^{-1} \pmod{m}$$

那么exgcd一下就出来了

当 $b_0=0$ 即 $m \mid b$ 时，分类讨论

• 当 $m \mid a$ 时， $\forall c \in \Z,bc \equiv a \pmod{m}$ 恒成立，题目保证了没有这种情况
• 当 $m\nmid a$ 时，$bc \equiv a \pmod{m}$ 无解

因此特判 $b_0 = 0$ 的情况即可

注意读入 $a,b$ 的时候要一边读一边取模

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
const int mod=19260817;
int readint()
{
    char ch=gc();int res=0;
    while(!isdigit(ch))ch=gc();
    while(isdigit(ch))
    {
        res=(res<<1)+(res<<3)+(ch^48);
        res%=mod;
        ch=gc();
    }
    return res;
}
int exgcd(int a,int b,int &x,int &y)
{
    int d=a;
    if(!b)x=1,y=0;
    else d=exgcd(b,a%b,y,x),y-=a/b*x;
    return d;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int a,b;
    a=readint();b=readint();
    if(!b)return cout << "Angry!" << endl,0;
    int x,y;
    exgcd(b,mod,x,y);
    x=(x%mod+mod)%mod;
    cout << a*x%mod << endl;
    return 0;
}