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

· · 题解

算法介绍

有理数取余是因为整数取模不能做除法而打上的一个补丁。

对于正整数 m 和有理数 x，若 x=\dfrac pq，其中 p,q 互质，若 q,m 互质，我们定义 x 模 m 的结果为唯一满足 0\le r<m 的整数 r 满足 rq\equiv p\pmod m。可以证明这是存在且唯一的，并且就算 p,q 不互质，只要 q,m 互质，这个结果是不变的。

可以证明，有理数取模就可以加减乘除，其中除要满足除数与 m 互质（若 m 为素数，就是要求非零）。这里主要介绍算法，所以略去性质相关的证明。

根据题意，给定 p=19\, 260\, 817 和一个有理数 \dfrac ab，我们要找到唯一一个 0\le r<p 满足 rb\equiv a\pmod p。首先这个式子只和 a,b 在 {}\bmod p 意义下的值相关，因此可以同时读入和取模。接下来只需要枚举 r 就可以在 O(p) 的时间内通过本题。

正确性证明

这里主要来证一下 a,b 不互质的情况下也是对的。若 a,b 同乘 d，因为 rb\equiv a\pmod p，故 rbd\equiv ad\pmod p，即用 ad,bd 算的也是对的。

复杂度因为 0\le r<p 的整数 r 只有 p 个，所以复杂度是 O(p) 的（忽略读入时间）。

代码实现

本题还要求若 b\equiv 0,a\not\equiv0\pmod p 时输出 Angry!，此时对应了方程无解（除以零）的情况，因此找不到的时候输出即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=19260817;
ll getint()
{
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    ll ans=0;
    while(isdigit(c))
    {
        ans=(ans<<1)+(ans<<3)+c-'0';
        ans%=mod;
        c=getchar();
    }
    return ans;
}
int main()
{
    ll a=getint();
    ll b=getint();
    for(int i=0;i<mod;++i)
    {
        if(i*b%mod==a)
        {
             printf("%d\n",i);
             return 0;
        }
    }
    printf("Angry!\n");
    return 0;
}