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

声明：

前置芝士：

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

正解：

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

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

• 扩欧求逆元：
  已知求逆元时，我们会写出一个同余方程：$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;
}