P2613 【模板】有理数取余 讲解

xy_mc · 2025-03-07 13:12:02 · 题解

声明：

在接下来的讲述中，我会用 p 代表题中的模数 19260817。

前置芝士：

• 快读；
• 逆元；
• 扩展欧几里得。

正解：

• 读入：

  很显然，这道题输入的数太大了，根本不能用正常的方法输入，用字符串行不行呢？太麻烦了。所以我们考虑在输入时对其取模。还记得快读吗？我们只需要加一个取余就行了。如：

  inline int rd(){
    int x=0,ch=getchar();
    while(!isdigit(ch)&&ch!=EOF) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),x%=mod,ch=getchar();
    return x;
  }

解决了读入，剩下的就很简单了。

首先把题目中的式子改一下，如：

将除以 b 改为乘 b 的逆元，即乘 b^{-1}。接下来就要看看逆元如何求了。这里我采用的是扩展欧几里得求逆元。

• 扩欧求逆元：

  已知求逆元时，我们会写出一个同余方程：ax \equiv 1 \pmod b，解出的 x 即为 a 在模 b 意义下的逆元。在题中，用于求解 b 在模 p 意义下的逆元的方程是：bx \equiv a \pmod p，那如何解这个方程呢？很简单，将其改造一下：

  b x\equiv a \pmod p b x-p y=a

  由于 y 可以是任何数，所以可以写成：

  b x+p y=a

  转化为熟悉的样子：

  b x+p y=\gcd(b,p)

  求解过程：

  设：

  b x_1+p y_1 = \gcd(b,p) p x_2 + (b \bmod p)y_2 =\gcd(p,b \bmod p) \because \gcd(b,p) = \gcd(p,b \bmod p) \therefore b x_1+p y_1 = p x_2 + (b \bmod p)y_2 \because b \bmod p = b - ( \left\lfloor \frac{b}{p} \right \rfloor \times p) \therefore b x_1+p y_1 = p x_2 + (b - ( \left\lfloor \frac{b}{p} \right \rfloor \times p))y_2 b x_1 + p y_1 = b y_2 + p x_2 - \left\lfloor \frac{b}{p} \right \rfloor \times p y_2 b x_1 + p y_1 = b y_2 + p (x_2 - \left\lfloor \frac{b}{p} \right \rfloor \times y_2) \because b=b,p=p \therefore x_1=y_2,y_1=x_2 - \left\lfloor \frac{b}{p} \right \rfloor \times y_2

  把 x_2 和 y_2 不断代入递归求解，直至 \gcd 为 0，递归 x=1,y=0 回去求解。

  像这样求出来的 x 就是 b 在模 p 意义下的逆元了。

  最后用 a 乘 x 再取模就行了。

代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define rep(i,x,y) for(reg int i=x;i<=(y);++i)
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
using namespace std;
const int p=19260817;
inline int rd(){
    int x=0,ch=getchar();
    while(!isdigit(ch)&&ch!=EOF) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),x%=p,ch=getchar();
    return x;
}
int a,b,x,y;
void exgcd(int a,int b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    int t=x;
    x=y;
    y=t-(a/b)*y;
}
signed main(){
    a=rd();
    b=rd();
    if(b==0){  //分母不能为 0，故无解。
        cout<<"Angry!";
        return 0;
    }
    exgcd(b,p);
    x=(x%p+p)%p; //保证为正数
    cout<<a*x%p;
    return 0;
}