以下是my solution至 a problem on codechef .
我在我的计算机上获得了正确的输出,但在 codechef 上却没有。
我在我的代码中找不到错误。
问题是将数组除以其元素的 GCD 并打印它。
我编写了以下代码:
#include<stdio.h>
int main(void)
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int a[n],i,divisor,curr,r;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
divisor = a[0];
for(i=1;i<n;i++)
{
curr = a[i];
if(curr<divisor)
{
divisor = curr;
}
}
for(i=0;i<n;i++)
{
r = a[i]%divisor;
if(r != 0){
divisor = 1;
break;
}
}
for(i=0;i<n-1;i++)
{
printf("%d ",a[i]/divisor);
}
printf("%d\n",a[n-1]/divisor);
}
return 0;
}
t
是测试用例的数量。n
是数组的长度。a[n]
是数组。divisor
是数组中所有元素的 GCD。curr
是当前测试的数字。r
是余数。
示例输入
3
2 4 4
3 2 3 4
4 3 15 9 6
示例输出
1 1
2 3 4
1 5 3 2
最佳答案
您认为这是一个涉及 CGD(最大公约数)的练习,这是正确的。
但是你误解了如何计算 GCD。
它很少是数组中最小的元素。
例如:
15, 6, 9
最小的元素是 6
并且不是另一个元素的公约数(并且在您的情况下会选择 1
作为除数),但是 gcd本例为 3
您可以首先阅读一些有关计算 CGD 的信息。的一对元素。还有一个example implementation .
然后尝试找出如何计算数组中所有元素的 GCD。
这些提示可能会有所帮助
关于CodeChef 上的切割食谱练习,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38474610/