目录
1.乘法逆元定义
逆元是指一个可以取消另一给定元素运算的元素。
比如，在实数的加法中，任意实数 a 和它的相反数 -a，互为加法逆元。因为对于任意实数 x，加上a之后，再加上-a，仍然等于 x，换言之，-a取消了x和a的加法运算。
再比如，在实数的乘法中，任意不为0的实数b和它的倒数 编辑，互为乘法逆元。因为对于任意实数x，乘上b之后，在乘上
，仍然等于x，换言之，
取消了x 和 b 的乘法运算。
而在实际应用中，我们常常被要求对某一个质数取模，因此我们需要了解模意义下的乘法逆元运算。模运算下的乘法逆元定义：如果两个整数a 和 b 满足 ( a ∗ b − 1 ) mod p = 0，即 a ∗ b ≡ 1 ( mod p )。则称 a 和 b 互为模 p 的乘法逆元。
2.乘法逆元存在条件
a和p互质是a存在关于模p的乘法逆元b的充分必要条件。
3.求乘法逆元的方法
1.扩展欧几里德算法
算法具体作用：扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足裴蜀等式 ax + by = gcd(a,b)。
代码实现：
int exgcd(int a,int b,int &x,int &y)
{
if(b==0) {
x=1;y=0;
return a;
}
int r = exgcd(b,a%b,x,y);
int t = y;
y = x-(a/b)*y;
x = t;
return r;
} 2.费马小定理 + 快速幂
费马小定理：在所取得模p为质数的前提下，有，也就是有
。所以a在模p的时候的乘法逆元为
。
inline int quick_power(int a, int b, int p) {
int ans = 1;
a = (a % p + p) % p;
for (; b; b >>= 1) {
if (b & 1) ans = (a * ans) % p;
a = (a * a) % p;
}
return ans;
}
// quick_power(a, p-2, p) 即为 a 的乘法逆元。
3.线性求1到n中每个数的逆元
现在要求1到n中每个数i在模p时的乘法逆元。特别的，i = 1时，其乘法逆元i-1为1。
代码实现：inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (p-p/i)*inv[p%i]%p;
} 思路分析：
4.求任意n个整数的乘法逆元
s[0] = 1; for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p; sv[n] = quick_power(s[n], p - 2); for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p; for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;
4.补充练习题
思路：前缀和思想，模版类型的前缀和是用于处理多次查询区间[l,r]的数组的元素的和，而前缀和的思想可以在理解之后进行进一步的应用，前缀和的思想的核心为：可以记录某一种操作，并且有对应的逆向操作可以取消这种操作的影响。而在读完题目之后，我们很容易就会想到前缀和，但是问题在于本题是要取模，所以前缀和sum[r] / sum[l-1]就不再适合，而应该选择在取模运算的下的乘法逆元。
#define fi first
#define se second
#define pb(a) push_back(a)
#define Q 1000000
#define EXP 1.000000000000000
#define mod 1000000007
#define EPS 1E-12
#define m_p make_pair
#define ft first
#define PI 3.141****53589
#define sc second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline __int128 read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
ll fastpow(ll a,ll b,ll p)
{
ll res = 1;
while (b > 0)
{
if(b & 1)
{
res = res * a % p;
}
a = a * a % p;;
b >>= 1;
}
res %= p;
return res;
}
int get_inv(int x)
{
return fastpow(x,mod - 2,mod);乘法逆元
}
ll a[100010];
ll sum[100010];
int main()
{
// std::ios::sync_with_stdio(false);
int N,M;
cin>>N>>M;
for (int i = 1; i <= N; i++)
{
a[i] = read();
}
sum[0] = 1;
for (int i = 1; i <= N; i++)
{
sum[i] = sum[i-1] * a[i] % mod;
}
int l,r;
while (M--)
{
scanf("%d%d",&l,&r);
ll ans = sum[r] * get_inv(sum[l-1]) % mod;
printf("%lld\n",ans);
}
return 0;
} 
全部评论
(1) 回帖