Two Divisors CodeForces - 1366D(수론)

You are given n integers a1,a2,…,an.
For each ai find its two divisors d1>1 and d2>1 such that gcd(d1+d2,ai)=1 (where gcd(a,b) is the greatest common divisor of a and b) or say that there is no such pair.
Input The first line contains single integer n (1≤n≤5⋅105) — the size of the array a.
The second line contains n integers a1,a2,…,an (2≤ai≤107) — the array a.
Output To speed up the output, print two lines with n integers in each line.
The i-th integers in the first and second lines should be corresponding divisors d1>1 and d2>1 such that gcd(d1+d2,ai)=1 or −1 and −1 if there is no such pair. If there are multiple answers, print any of them.
Example Input 10 2 3 4 5 6 7 8 9 10 24 Output -1 -1 -1 -1 3 -1 -1 -1 2 2 -1 -1 -1 -1 2 -1 -1 -1 5 3 Note Let’s look at a7=8. It has 3 divisors greater than 1: 2, 4, 8. As you can see, the sum of any pair of divisors is divisible by 2 as well as a7.
There are other valid pairs of d1 and d2 for a10=24, like (3,4) or (8,3). You can print any of them. 사고방식: 하나의 수 x, x= (p1^k1)*(p2^k2)*(p3^k3)...*(pn^kn).우리는 d1=(p1^k1), d2=x/d1을 명령한다.우리는 d1+d2가 x에 대한 모든 질인자 p1, p2...pn을 모두 제거하지 않는 것을 발견할 수 있다. 즉, (d1+d2)%p1≠0(d1+d2)%p2≠0(d1+d2)%p3≠0...
그러면 이 문제에 대해 우리는 1e7 내의 모든 수의 첫 번째 질인자를 열거한 다음에 d1과 d2를 계산할 수 있다. 만약에 d2==1이면 모두 -1이면 된다.명백히 알 수 있듯이 소수도 모두 -1이다.
코드는 다음과 같습니다.

#include
#define ll long long
using namespace std;

const int maxx=5e5+100;
const int maxm=1e7+100;
int a[maxx];
int ans[2][maxx];
int prime[maxm];
int vis[maxm];
int num[maxm];
int n;

inline void init()
{
	memset(vis,0,sizeof(vis));
	memset(prime,-1,sizeof(prime));
	memset(num,0,sizeof(num));
	for(int i=2;i<maxm;i++)
	{
		if(vis[i]==0)
		{
			prime[i]=1;
			for(int j=i+i;j<maxm;j+=i)
			{
				if(num[j]==0) num[j]=i;
				vis[j]=1;
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	init();
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		if(prime[a[i]]==1) ans[0][i]=ans[1][i]=-1;
		else
		{
			int x=a[i];
			int cnt=0;
			while(1)
			{
				if(x%num[a[i]]==0) 
				{
					cnt++;
					x/=num[a[i]];
				}
				else break;
			}
			if(x==1) ans[0][i]=ans[1][i]=-1;
			else
			{
				ans[0][i]=pow(num[a[i]],cnt);
				ans[1][i]=x;
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[0][i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++) cout<<ans[1][i]<<" ";cout<<endl;
	return 0;
}

열심히 힘내라 a야,(o)/~