乘法逆元1
这里有两种方法求逆元其实我只会两种qwq:
在这里放一个线性的式子:
[inv_i = p-(pdiv i) imes inv_{p\%i}\%p
]
原理我也不懂orz。
啊是的这是第一种方法。
另一种方法用到了费马小定理,结论是:
在模数(p)为质数的情况下:
[a^{-1}equiv a^{p-2} (mod~~p)
]
不会证。
然后我们用快速幂求一下即可。
不过在这道题里用第二种方法会T,必须用线性的求法。
乘法逆元2
我们Tethys真的是太厉害啦!!!!
如果用线性求逆元的方法,我们需要求出从(1)到(a_{max})的所有逆元。
然而(a_{max})上限为(10^{9}),这种做法显然是不可行的。
有另一种求逆元的方法好像叫离线求逆元??:
首先逆元是完全积性的,我们要知道(a_i)的前缀积的逆元就是逆元的前缀积。
所以我们在输入的时候顺便求一下前缀积,然后有这么两个式子:
[式子1:a_{i}^{-1}=pre_{i}^{-1} imes pre_{i-1}(1leq ileq n)
]
[式子2:pre_{i-1}^{-1} = pre_{i}^{-1} imes a_i (1leq i< n)
]
推式子:
式子是怎么推的,这一步可以跳过,因为太简单qwq:
式子2:
第二个好推所以我们先推第二个 (pre_{i-1}^{-1} = pre_{i}^{-1} imes a_i)
首先逆元的前缀积是这样的:
[pre_i^{-1} = a_{1}^{-1} imes a_{2}^{-1} imes ... imes a_{i}^{-1}
]
因为(a^{-1} = frac{1}{a}),
所以可以变成这样的形式:
[pre_i^{-1} = frac{1}{a_1 imes a_{2} imes ... imes a_{i}}
]
显然:
[pre_{i-1}^{-1} = pre_i^{-1} imes a_i = frac{1}{a_1 imes a_{2} imes ... imes a_{i}} imes a_i = frac{1}{a_1 imes a_{2} imes ... imes a_{i-1}}
]
所以:
[pre_{i-1}^{-1} = pre_{i}^{-1} imes a_i
]
式子1:
接下来推第一个式子(a_{i}^{-1}=pre_{i}^{-1} imes pre_{i-1})
因为:
[a_{i}^{-1} = frac{1}{a_i}
]
因为前缀积的逆元可以变成这样:
[pre_i^{-1} = frac{1}{a_1 imes a_{2} imes ... imes a_{i}}
]
把式子1展开相乘一下:
[pre_i^{-1} imes pre_{i-1} = frac{1}{a_1 imes a_{2} imes ... imes a_{i}} imes a_1 imes a_{2} imes ... imes a_{i-1} = frac{1}{a_i}
]
所以:
[a_{i}^{-1}=pre_{i}^{-1} imes pre_{i-1}
]
然后我们就推完了orz。
我们就可以根据这个两个式子线性求出逆元的前缀积,但是首先要(log)的求一下(pre_n)的逆元。
代码:
#include <bits/stdc++.h>
using namespace std;
template<typename temp>temp read(temp &x){
x = 0;temp f = 1;char ch;
while(!isdigit(ch = getchar())) (ch == '-') and (f = -1);
for(x = ch^48; isdigit(ch = getchar()); x = (x<<1)+(x<<3)+(ch^48));
return (x *= f);
}
template <typename temp, typename ...Args>void read(temp& a, Args& ...args){read(a), read(args...);}
const int maxn = 5e6+10;
long long n, p, k, ans, pre[maxn], inv_pre[maxn], a[maxn];
long long fast(long long x, long long y, long long p){
long long ans = 1;
while(y){
if(y&1) ans = ans*x%p;
x = x*x%p;
y >>= 1;
}
return ans%p;
}
signed main(){
read(n, p, k);pre[0] = 1;
for(int i = 1; i <= n; i ++) pre[i] = pre[i-1]*read(a[i])%p;//求前缀积
inv_pre[n] = (fast(pre[n], p-2, p));//求出pre[n]的逆元
for(int i = n; i >= 1; i --) inv_pre[i-1] = inv_pre[i]*a[i]%p;//求出逆元的前缀积
for(int i = n; i >= 1; i --) ans = (ans + inv_pre[i]*pre[i-1]%p)*k%p;//式子一求出a[i]的逆元
printf("%lld", ans);
return 0;
}