[数据结构与算法]牛牛做数论（转化，质数）

Linking

题目：

定义 $H(x)=\frac{?(x)}{x}$，$?(x)$ 表示欧拉函数。

思路：

有公式：$\phi (x)=x?\prod (1?\frac{1}{p_i})$，那么 $H(x)=\prod (1?\frac{1}{p_i})$。

于是题目转化为：
求 [2, n] 中的一个数x，满足其 ∏(1-1/pi) 是所有数中的最小的。如果有多个数，输出最小一个。
满足其 ∏(1-1/pi) 是所有数中的最大的。如果有多个数，输出最大一个。

• (1 - 1/pi) 是小于 1 的，所以越乘越小，而且越往后，这个值越大。 所以为了使其乘积最小，就尽量用前面小的，尽量多的乘。
  为了满足这些数是x的质因数，那么x就可以用这些质因数相乘来确定，乘到不超过n。
• (1 - 1/pi) 越往后越大，而如果两个小于 1 的数相乘势必比这两个都小，所以就直接用最大的一个。
  那么就是只有一个最大的不超过n的质因子，那么 x 便就是这个质因子。
  从n一直递减，判断是不是质数。（可能因为两个质数之间没隔太远，所以直接遍历就行）

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m, k; 
int a[N], prim[N], f[N];
int cnt;

void Prim() //这里用不了多少质数相乘就会超过1e9了，直接列也行
{
	m = 100010;
	for(int i=2;i<=m;i++)
	{
		if(!f[i]) prim[++cnt]=i;
		for(int j=1;prim[j]<=m/i;j++)
		{
			f[prim[j]*i] = 1;
			if(prim[j] % i == 0) break;
		}
	}
}

bool isP(int x)
{
	if(x==0 || x==1) return 0;
	for(int i=2;i<=x/i;i++)
	{
		if(x%i==0) return 0;
	}
	return 1;
}

signed main(){
	Ios;
	
	Prim();
	
	cin>>T;
	while(T--)
	{
		cin>>n;
		
		if(n==1){
			cout<<-1<<endl;continue;
		}
		
		int x = 1;
		for(int i=1;i;i++)
		{
			if(x * prim[i] <= n) x*=prim[i];
			else break;
		}
		cout << x << " ";
		
		while(!isP(n)) n--;
		cout << n << endl;
	}
	
	return 0;
}