70pts MLE求助
查看原帖
70pts MLE求助
173077
William_Wang_楼主2023/1/20 10:37

n106n\le 10^6 , 112n2n 每个数至多 77 个不同质因数 , 最多 7×2×1067\times 2\times 10^6 个数 , 请问这样会爆吗

#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;
}

2023/1/20 10:37
加载中...