第一周 F-乘法逆元2

题目描述

这可能是一道模板题。

给定 n 个正整数 ai，求每个数在模 pp 意义下的乘法逆元。

提示：请使用高效的读入方式。

思路

代码

#include <iostream>

#define ll long long
using namespace std;

const int N = 5e6 + 10;
const int p = 1e9 + 7;
const int M = 998244353;

//函数返回类型前加上关键字inline，即可以把函数指定为内联函数。 这样可以解决一些频繁调用的函数大量消耗栈空间（栈内存）的问题。
inline ll fast_qow(ll a,ll b){
    ll ans1 = 1;
    while(b){
        if(b & 1){ ans1 = (ans1*a) % p;}
        a = (a * a) % p;
        b >>= 1;
    }
    return ans1;
}

ll a[N], S[N], S_inv[N], a_inv[N],m[N];
//n个数 n个数的乘积 n个数逆元的乘积 n个数的逆元 M的n次方
ll n, ans;

int main(){
    cin >> n;
    for(int i = 1; i<= n; i++){
        cin >> a[i];
    }

    m[0] = 1LL;
    //1LL会在运算时把后面的临时数据扩容成long long类型，再在赋值给左边时转回int类型
    for(int i = 1; i < n; i++){
        m[i] = (m[i-1] * M) % p;
    }

    S[0] = 1;
    for(ll i = 1; i <= n; i++){
        S[i] = (S[i - 1] * a[i]) % p;
    }

    S_inv[n] = fast_qow(S[n], p-2);//求总积的逆元
    //将S_inv的1~n-1补齐
    for(int i = n; i >= 1; i--){
        S_inv[i - 1] = (S_inv[i] * a[i]) % p;
    }

    //求每一个数的逆元然后加到ans
    for(int i = 1; i <= n; i++){
        a_inv[i] = (S_inv[i] * S[i - 1]) % p;
        
        //求Σ (a_inv*M^n-1) mod p
        a_inv[i] = (a_inv[i] * m[n - i]) % p;
        //ans = (ans + (a_inv[i]*m[n-i])%p) % p;
        ans = (ans + a_inv[i]) % p;
    }
    cout << ans % p << endl;
    return 0;
}