P2613 题解

· · 题解

题目传送门

注：在本篇题解中，除数 b 写作有理数 c 写作 x。

算法介绍

本题需使用逆元。

逆元即对于同余方程 ax\equiv1\pmod p，则 x 为 a\bmod p 的逆元，记作 a^{-1}。若其满足 a\nmid p，则 a^{-1}\equiv a^{p-2}\pmod p。

本题中 a 和 b 为较大的整数，可以用快读来读入，并对 19260817 取模。

正确性证明

根据费马小定理可知 a^{p-1}\equiv1\pmod p。

费马小定理证明：

构造集合 S=\{1,2,3,\dots,p-1\}，同时构造集合 S'=\{a,a\times2,a\times3,\dots,a\times(p-1)\}。

由于 a\nmid p，所以 a 和 p 互质。因此对于所有不同的 u 和 v，一定满足 a\times u\not\equiv a\times v\pmod p。所以 S' 是模 p 意义下的完全剩余系，且没给元素都与 S 中的某个元素同余。

然后计算 S 的积 \prod S=1\times2\times3\times\dots(p-1)=(p-1)!\pmod p，以及 S' 的积 \prod S'=a\times(a\times2)\times(a\times3)\times\dots(a\times(p-1))=a^{p-1}\times(p-1)!\pmod p。

因为 S 和 S' 都是模 p 意义下的完全剩余系，所以两集合的积同余，即 (p-1)!\equiv a^{p-1}\times(p-1)!\pmod p。

最后化简得 a^{p-1}\equiv1\pmod{p}。

证出费马小定理，可以推出逆元式子：

1\equiv1\pmod{p}\\ a^1\times a^{-1}\equiv a^{p-1}\pmod{p}\\ a^{-1}\equiv a^{p-2}\pmod{p}

对于幂的计算，可以使用快速幂。

时间复杂度 \mathcal{O}(\log A)。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=19260817;
int read(){
    int x=0;
    char f=1,ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x*10+ch-'0')%MOD; //这里对 x 进行取模操作
        ch=getchar();
    }
    return x*f;
}
int q_pow(int a,int b,int MOD){ //快速幂
    int res=1;
    while(b){
        if(b&1)
            res=res*a%MOD;
        b>>=1;
        a=a*a%MOD;
    }
    return res;
}
signed main(){
    int a=read(),b=read();
    if(!b) //除数 b 不能为 0
        return printf("Angry!\n"),0;
    printf("%lld\n",a*q_pow(b,MOD-2,MOD)%MOD); //逆元
    return 0;
}