算法1

$O(n^2)$

C++ 代码

#include<iostream>
#include<unordered_map>

using namespace std;
const int mod=1e9+7;
unordered_map<int,int>count;
void isprme(int x){
    for(int i=2;i<=x/i;++i){
        if(x%i==0){
            while(x%i==0){
                x=x/i;
                count[i]++;
            }
        }


    }
    if(x>1)count[x]++;


}

int main(){
    int n;
    cin>>n;

    for(int i=0;i<n;++i){
        int x;
        cin>>x;
        isprme(x);
    }
   long long sum=1;
    for(auto p:count){
        long long temp=1;
        long long t=1;
        //秦九昭算法，这个序列每次都平方一次，相当于序列中的数全体进一位（次方加一位）
        //最后一位再补个1，相当于求次方和
        while(p.second--)temp=(temp*p.first+1)%mod;

       sum=(sum*temp)%mod;

    }
    cout<<sum<<endl;

    return 0;
}