洛谷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;
}