专题班前缀和练习题 - A - 智乃酱的区间乘积

前缀积
要求Ai * A(i+1) * A(i+2) * ... * A(j)
只需要知道前缀积 B(j) 和 B(i-1)，Ai * A(i+1) * A(i+2) * ... * A(j) = B(j) / B(i-1)
在取模的意义下
除法 = 乘法逆元

#include <bits/stdc++.h>
using namespace std;

typedef  long long ll;
const int maxn = 1e5 + 10;
const ll MOD = 1e9 + 7;
ll a[maxn], x;
int N, M;
int l, r;

ll pow_mod(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

void extgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll inverse(ll a,ll n){
    ll d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &M);
    a[0] = 1;
    for(int i = 1; i <= N; i++){
        scanf("%lld", &x);
        a[i] = (a[i - 1] * x) % MOD;
    }
    while(M--){
        scanf("%d%d", &l, &r);
        //printf("%lld\n", a[r] * pow_mod(a[l - 1], MOD - 2, MOD) % MOD);
        printf("%lld\n", a[r] * inverse(a[l - 1], MOD) % MOD);
    }
    return 0;
}