如何使我的CodeChef解决方案代码更快

Question

我是第一学期的初学者。我一直在练习"代码厨师"，但遇到了这个问题。他们要求减少我代码的执行时间。问题如下：

梅利奥达斯和潘基文正在为巧克力而争吵。Meliodas有X块巧克力，Ban有Y块。巧克力数量较少的人吃的巧克力数量与其他人收藏的巧克力数量一样多。这场美食大战一直持续到他们要么有相同数量的巧克力，要么至少有一个人没有巧克力。你能帮伊丽莎白预测一下他们战争结束后会剩下多少巧克力吗？

输入：第一行将包含T，测试用例的数量。然后是测试用例。每个测试用例包含一行输入，其中包含两个整数X、Y，分别是Meliodas和Ban的巧克力数量。

输出：对于每个测试用例，在一行中输出Ban和Meliodas停止战斗后剩余的巧克力数量。

样本输入：

3
5 3
10 10
4 8

样本输出：

2
20
8

我的代码如下：

#include <iostream>
using namespace std;
int main() 
{
unsigned int t,B,M;
cin>>t;
while(t--)
{
cin>>M>>B;
if(B==M)
{
cout<<B+M<<endl;
}
else
{
for(int i=1;B!=M;i++)
{
if(B>M)
B=B-M;
else
M=M-B;
}
cout<<M+B<<endl;
}
}
return 0;
}

Answer 1

假设B和M与0不同，则此算法对应于欧几里得算法的一个版本。因此，您可以简单地：

std::cout << 2 * std::gcd(B, M) << "n";

如果其中至少有一个数量等于0，则只打印B + M。

Answer 2

在意识到您的代码是正确的之后，我想知道哪里可以改进算法。我意识到，从同伴那里吃尽可能多的巧克力实际上接近于模运算。如果两个数字都很接近，减号运算可能比模一运算略快，但如果一个数字很高，而另一个是1，你会立即得到它，而不是循环很多次。。。

防止愚蠢错误的关键是要意识到，如果模为0，那意味着高数值是小数值的倍数，我们必须立即停止写入低数值的两倍。

需要注意的是，如果其中一个初始计数为0，则总数永远不会改变。

所以外环应该变成：

if(B==M || B == 0 || M == 0)
{
cout<<B+M<<"";
}
else {
for (;;) {
if (M < B) {
B = B % M;
if (B == 0) {
cout << M * 2 << 'n';
break;
}
}
else {
M = M % B;
if (M == 0) {
cout << B * 2 << 'n';
break;
}
}
}
}
...

注意：这里不可能有无限循环，因为模确保例如是M > B > 0' afterM=M%Byou will haveB>M>=0and as the case==0`明确处理时，循环数不能大于下限。