超时咋改，求助

题目描述

已知正整数i,j 的最小公倍数为n ，求 max(i,j)的最小值。

输入

输入一行：一个数 n （n≤1e12）

输出

输出一行一个数，表示max(i,j)的最小值。

样例输入 Copy

样例输出 Copy 2

提示

对于10%的数据，1 ≤ n ≤ 30；

对于38%的数据，1 ≤ n ≤ 200000；

对于100%的数据，1 ≤ n ≤ 1012；

本人代码（暴力）

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a=111111111,b=111111111;
int gcb(int x,int y)
{
	int q=x;
	while(q=x%y)
	{
		x=y;
		y=q;
	}
	return y;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n/2;i++)
	{
		for(int j=1;i*j<=n;j++)
		{
			if((i*j/gcb(i,j))==n)
			{
				if(max(i,j)<max(a,b))
				{
					a=i,b=j;
				}
			}
		}
	}
	printf("%d",max(a,b));
	return 0;
}

讨论操作

回复

相关推荐

超时咋改，求助