Ограничение времени, превышающее в тестовом случае для моего решения. Что не так с моим решением?

Codeforces 119A- http://codeforces.com/problemset/problem/119/A

Мое решение:

#include<iostream>
using namespace std;
int a,b,i,n;
int gcd(int x,int y)
{
 int z,c;
 c=min(x,y);
 for(i=1;i<=c;i++)
 {
 if(((x%i)==0)&&((y%i)==0))
 z=i;
 }
 return z;
}
int main()
{
 cin>>a>>b>>n;
 while(1)
 {

 if(n</iostream>
<p> Я не знаком с ограничениями времени. Мое решение дает правильный результат во время работы на моем компьютере в обычное время. Что я должен изменить в своем решении для его запуска с ограниченным сроком? Должен ли я воздерживаться от использования определенных пользователем функций? Испытательные случаи - 3,5,9 и 1,1 100.</p>
1 ответ

Ваш код определенно точным и приводит к правильному ответу, но есть несколько незначительных улучшений, которые можно было бы сделать для повышения эффективности и успеха в прохождении срока.

  1. Не вычисляйте GCD дважды внутри цикла while. GCD - это дорогостоящий алгоритм, так как его запуск вдвое удваивает общее время завершения вашей программы. Это, вероятно, самое важное исправление, которое вы можете сделать, чтобы ваша программа не приводила к TLE.
  2. Потенциально оптимизируйте свой алгоритм GCD, хотя это не обязательно для передачи всех тестовых файлов (показано ниже)

Реализация, которая использует gcd только один раз и передает все тестовые файлы в кодовых выражениях, может выглядеть следующим образом (представление здесь):

#include <iostream>
using namespace std;

int gcd(int, int);

int main()
{
 int a, b, n;
 cin >> a >> b >> n;
 while (1) {
 n -= gcd(a, n);
 if (n == 0) {
 cout << "0" << endl;
 return 0;
 }
 n -= gcd(b, n);
 if (n == 0) {
 cout << "1" << endl;
 return 0;
 }
 }
}

int gcd(int u, int v)
{
 int t;
 while ((t = u % v) != 0) {
 u = v;
 v = t;
 }
 return v;
}
</iostream>

licensed under cc by-sa 3.0 with attribution.