A 智乃酱的区间乘积
考虑前缀积。
令 表示 ,则 可表示为 ,预处理出数组,查询的时候套上一个乘法逆元即可。
下面是关于乘法逆元,我们可以利用费马小定理 如果 是质数,且 即 互质,则 所以可推出
。又因为
对比两个式子即可得出在模 意义下 和 同余。
my code:
#include <bits/stdc++.h> #define ll long long using namespace std; const int mod = 1e9 + 7,maxn = 1e5 + 10; int n,m; ll a[maxn]; ll q_pow(ll x,ll y){ ll ans = 1; while(y){ if(y & 1) ans = ans * x % mod; x = x * x % mod; y >>= 1; } return ans % mod; } int main(){ scanf("%d%d",&n,&m); a[0] = 1; for(int i = 1;i <= n;i++){ scanf("%lld",&a[i]); a[i] = a[i] * a[i - 1] % mod; } int l,r; while(m--){ scanf("%d%d",&l,&r); printf("%lld\n",a[r] * q_pow(a[l - 1],mod - 2) % mod); } return 0; }
std:
#include<bits/stdc++.h> using namespace std; const int MAXN = 300005; const long long mod = 1e9 + 7; long long quickpow(long long x, long long y, long long MOD = 9223372036854775807LL) { long long ans = 1; while (y) { if (y & 1) { ans = (x * ans) % MOD; } x = (x * x) % MOD; y >>= 1; } return ans; } long long get_inv(long long x) { return quickpow(x, mod - 2, mod); } int n, l, r, m; long long a[MAXN], premul[MAXN]; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); } premul[0] = 1; for (int i = 1; i <= n; ++i) { premul[i] = premul[i - 1] * a[i] % mod; } while (m--) { scanf("%d %d", &l, &r); printf("%lld\n", premul[r]*get_inv(premul[l - 1]) % mod); } return 0; } /* 5 3 5 2 3 10 6 1 5 2 3 2 5 */