Question

ACM提交的时候 出现runtime error，代码如下，不解，是为什么

输入：The greatest common divisor and The least common multiple of two integers a and b
输出：the smallest sum of a and b.（若不存在a和b,则输出-1）
////////////////////////////////////////////////

提交的时候，出现runtime error

Runtime Error:Killed
Runtime Error:Killed
Runtime Error:Floating point exception
Runtime Error:Killed
Runtime Error:Killed

//////////////////////////////////////////////////

#include<stdio.h>
int fun(int c,int d,int a,int b)/*将求得的a,b的最大公约数将 与c、d比较 看是否相等 若不等 则 return -1 */
{
int temp1,max,t1,t2;
int s,min,temp2,f=0;
s=a*b,t1=a, t2=b;
if(a<=b)
{ temp1=a;a=b;b=temp1; }
while(b!=0)
if(a%b==0)
{ max=b;break; }
else { temp1=a%b; a=b; b=temp1;}
temp2=max;
min=s/temp2;
if(max==c && min==d)
return t1+t2;
else return -1;
}
int main()
{
int G,L; //maybe最大公约数和最小公倍数（已知）
int i,j,k=0,a,b,f=0,s=0,t;
int num[10000],min; //num[10000]用来存放a+b的值
while(scanf("%d%d",&G,&L)!=EOF)
{
k=0,f=0,s=0;
t=L>G?L:G;
for(i=1;i<=t;i++)
for(j=i,k;j<=G*L;j++) //原数在i,j的范围里变化
{
if(L>G) s=fun(G,L,i,j);
else s=fun(L,G,i,j);
if(s!=-1)
{
num[k++]=s;
f=1;
min=num[0];
}
}
for(i=0;i<k;i++)
{
if(num[i]<min) //在num数组中找到最小的a+b值
min=num[i];
}
if(f==0) printf("-1\n");
else printf("%d\n",min);
}
return 0;
}

Answer 1

int fun(int c, int d, int a, int b)
/*将求得的a,b的最大公约数将 与c、d比较 看是否相等 若不等 则 return -1 */
{
	int temp1, max, t1, t2;
	int s, min, temp2, f = 0;
	s = a*b, t1 = a, t2 = b;
	while (b != 0) {
		temp1 = a % b;
		a = b;
		b = temp1;
	}
	max = a;
	min = s / max;
	if (max == c && min == d)
		return t1 + t2;
	else return -1;
}

我把fun改了一下，你再试试

这是我自己写的答案

#include <stdio.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int dfs(int item[], int num, int index, int mul, int temp) {
	int ans1, ans2;
	if (temp * temp > mul) return -1;
	if (index == num) return temp;
	ans1 = dfs(item, num, index + 1, mul, temp*item[index]);
	ans2 = dfs(item, num, index + 1, mul, temp);
	return max(ans1, ans2);
}

int main() {
	int G, L, mul, i, item[100], num, temp, maximum;
	while (scanf("%d%d", &G, &L) == 2) {
		if (L % G != 0) {
			puts("-1");
			continue;
		}
		mul = L / G;
		num = 0;
		for (i = 2; i <= mul; i++) {
			if (mul % i == 0) {
				temp = 1;
				while (mul % i == 0) {
					temp *= i;
					mul /= i;
				}
				item[num++] = temp;
			}
		}
		mul = L / G;
		maximum = dfs(item, num, 0, mul, 1);
		printf("%d\n", G*(maximum + mul / maximum));
	}
}

追问

好激动！！！你写的通过了！！！

////////////////////////////////////////////////////////////////////////////////////////////

我把你改过的fun放上去了 结果是TLE50%

还有就是我刚刚自己另写了一个 出现的也是TLE 你可以再帮我看下吗？谢谢了！

抱歉 我只能截图了 说字数太多

追答

第二个我觉得挺好的，不知道是不是%I64d的问题，你可以试试%lld

追问

第二个挺好是因为有百度←_←
我换了一下，是TLE 27% ╮(╯▽╰)╭ 真劳神~
为什么你的可以通过？有没有可能是递归的问题？

追答

那你试试把最大公约数那个改成非递归版本

我的算法不一样，我用了深度优先搜索