n≤106 , 1 到 2n 每个数至多 7 个不同质因数 , 最多 7×2×106 个数 , 请问这样会爆吗
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6+5;
int n, mod, v[MAXN<<1], cnt[MAXN<<1];
vector <int> P[MAXN<<1];
int qpow(int a,int b)
{
int res = 1, base = a;
while(b)
{
if(b & 1) res *= base, res %= mod;
base *= base, base %= mod;
b >>= 1;
}
return res;
}
signed main()
{
cin >> n >> mod;
for(int i=2;i<=(n<<1);i++)
{
if(!v[i])
{
P[i].push_back(i);
for(int j=i+i;j<=(n<<1);j+=i) v[j] = 1, P[j].push_back(i);
}
}
for(int i=n+2;i<=(n<<1);i++)
for(auto j : P[i])
{
int x = i;
while(x && x%j==0) cnt[j]+=1, x/=j;
}
for(int i=1;i<=n;i++)
for(auto j : P[i])
{
int x = i;
while(x && x%j==0) cnt[j]-=1, x/=j;
}
int res = 1;
for(int i=1;i<=(n<<1);i++)
{
if(cnt[i]) res *= qpow(i,cnt[i]), res %= mod;
}
cout << res;
return 0;
}