【模板】模意义下的乘法逆元

定义

若 \(\gcd(a,m)=1\)，则存在 $a'\in\mathbb{Z} $，使得 \(a\times a'\equiv 1\pmod m\)，\(a'\) 称为 \(a\) 对模 \(m\) 的数论倒数，或者称 \(a'\) 为模 \(m\) 的逆元。
接下来我要证明一件事情，我看很多题解里都没有证明，那就是题目让我们输出 \(1\) 到 \(n\) 这 \(n\) 个整数模 \(m\) 的数论倒数，但是对于每个数真的都有数论倒数吗？答案是肯定的，接下来来证明：
首先 \(\left\{1,2,\dots,m\right\}\) 为模 \(m\) 的完系，因为 \(\gcd(a,m)=1\) 所以 \(\left\{a,2a,\dots,ma\right\}\)  也为模 \(m\) 的完系，所以这里面一定存在某一项模 \(m\) 余 \(1\) ，即存在 \(a'\in \left\{1,2,\dots,m\right\}\) 使得 \(a\times a'\equiv 1\pmod m\)。
解法

题目中说明了 \(p\) 是质数，但是我们需要知道适用于任何情况的解法，就是扩展欧几里得解法，这里不多加赘述了，这里作者介绍线性递推解法。
我们设 \(k=[\frac{p}{i}],p=ki+q\) 。所以 \(ki+q\equiv0\pmod p\)，那么 \(k\times i\times (i^{-1}\times q^{-1})+q\times (i^{-1}\times q^{-1})\equiv0\pmod p\)，所以 \(k\times q^{-1}+i^{-1}\equiv0\pmod p\)，那么 \(i^{-1}\equiv-k\times q^{-1}\pmod p\)，也就是说 \(i^{-1}\equiv-[\frac{p}{i}]\times q^{-1}\pmod p\)，用这个结论我们就可以求出 \(1\) 到 \(p-1\) 的逆元了！
使用时我们调用 \(f_a\) 即可，如果 \(a>p\) 那么就调用 \(f_{a \bmod p}\)。
这里给出模板题目：link。
代码

[code]#include#define I using#define AK namespace#define IOI std#define i_ak return#define ioi  0#define i_will signed#define ak main#define IMO ()#define int long long#define double long doubleI AK IOI;int n,p,f[3000005];i_will ak IMO{        //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);        //freopen("","r",stdin);        //freopen("","w",stdout);        cin>>n>>p;        f[1]=1;        cout