赛时写了个线性筛还写了个二分平方根 WA*10 AC*6 没调出来 /dk

如果是平方根写错了我就真寄了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n;
int pri[1000001],now;
bool vis[1000001],prime[1000001];
int pfg(int n) {//平方根
	int l = 1,r = sqrt(n)+10;
	while(l<=r) {
		int mid = (l+r)/2;
		if(mid*mid==n) {
			return mid;
		} else if(mid*mid<n) {
			l = mid+1;
		} else r = mid-1;
	}
	return -1;
}
signed main() {
	for(int i = 2; i<=1e6; i++) {//线性筛预处理
		if(!vis[i])prime[i] = 1,pri[++now] = i;
		for(int j=1; j<=now&&pri[j]*i<=1e6; j++) {
			vis[pri[j]*i] = 1;
			if(i%pri[j]==0) break;
		}
	}
	cin>>t;
	while(t--) {
		cin>>n;
		for(int q = 1; q<=1e6; q++) {//枚举q
			int p;
			if(!prime[q]) continue;/不是质数直接退出
			if(n%q==0) p = n/q;
			else continue;
			int ans = pfg(p);
			if(ans==-1) continue; 
			if(ans*ans*q==n) {//判断
				cout<<ans<<' '<<q<<endl;
				break;
			}
		}
	}
	return 0;
}