Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:在HOJ上过了的，在这儿TLE

Posted by htwc at 2014-02-02 22:44:25 on Problem 2429
In Reply To:在HOJ上过了的，在这儿TLE Posted by:javawin at 2010-08-20 21:38:56
```等等不对，你这样枚举可能达到10^9肯定要超时啦！我的方法你可以看下（虽然也超了）
#include <iostream>
#include <cstdio>

using namespace std;

long long gcd,lcm,k;
long long a[50],cnt;
long long res,mini;

void dfs(long long depth,long long t)
{
if(depth==cnt+1)
{
if(t+k/t<mini)
{
res=t;
mini=t+k/t;
}
return;
}

dfs(depth+1,t*a[depth]);
dfs(depth+1,t);
}

int main()
{
while(scanf("%lld%lld",&gcd,&lcm)!=EOF)
{
cnt=0; mini=0x7fffffffffffffffll;

k=lcm/gcd;
if(k==1)
{
printf("%lld %lld\n",gcd,lcm);
continue;
}

for(long long tmp=k,cur=2;tmp-1;cur++)
{
if(cur*cur>=tmp){a[++cnt]=tmp;break;}
if(tmp%cur)continue;

a[++cnt]=1;
while(!(tmp%cur))
{
a[cnt]*=cur;
tmp/=cur;
}
}

dfs(1,1);

long long res1=gcd*res,res2=lcm/res;
printf("%lld %lld\n",min(res1,res2),max(res1,res2));
}

return 0;
}
```

Followed by:

User ID:
Title:

Content: