CF1285C【黄】-思路题

也是一道思路题，甚至没做对，看来今天脑子有点昏，明个再说

正确代码

#include <iostream>
using namespace std;
inline long long gcd(long long a,long long b){//最大公因数
	return b?gcd(b,a%b):a;
}
inline long long lcm(long long a,long long b){//最小公倍数
	return a/gcd(a,b)*b;//防止溢出
}
inline long long max(long long a,long long b){//求最大值
	return a>b?a:b;
}
long long x,a,b,q,maxx;
int main(void){
	cin>>x;
	for(long long i=1;i<=x/i;i++){//枚举
		if(x%i){//不是x因数就跳过
			continue;
		}
		if(lcm(i,x/i)==x){//满足条件的就取
			maxx=max(maxx,i);
		}
	}
	cout<<maxx<<" "<<x/maxx;//输出
}

错误且麻烦的代码（未考虑到从小到大选取质因数所成出来的因数并非全部因数，应该直接考虑全部因数，这样不仅正确而且简单）

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#define int long long
using namespace std;
long long X,X0;
unordered_map<int,int>b;
inline long long gcd(long long a,long long b){//最大公因数
	return b?gcd(b,a%b):a;
}
inline long long lcm(long long a,long long b){//最小公倍数
	return a/gcd(a,b)*b;//防止溢出
}
signed main()
{
	cin>>X;X0=X;
	while(1)
	{
		int f=0;
		for(int i=2;i<X;i++)
		{
			if(X%i==0)
			{
				if(b.find(i)==b.end())b[i]=0;
				b[i]++;
				X/=i;
				f=1;
				break;
			}
		}
		if(f==0)break;
	}
	if(b.find(X)==b.end())b[X]=0;
	b[X]++;
	if(X==X0)
	{
		cout<<1<<' '<<X0<<endl;
		return 0;
	}
	long long a=1,minmax=X0,ans1=-1,ans2=-1;
	for(int i=2;i<X0;i++)
	{
		if(b.find(i)!=b.end())
		{
			while(b[i]>0)
			{
				a*=i;
				b[i]--;
				if(lcm(a,X0/a)==X0)
				{
					if(minmax>max(a,X0/a))
					{
						minmax=max(a,X0/a);
						ans1=a,ans2=X0/a;
					}
				}
				if(a>minmax)break;
			}
			if(a>minmax)break;
		}
			
	}
	if(ans1!=-1) cout<<min(ans1,ans2)<<' '<<max(ans1,ans2)<<endl;
	else cout<<1<<' '<<X0<<endl;
	return 0;
}
/*524323425
  wrong9091 57675
  right19225 27273*/