Форум программистов, компьютерный форум CyberForum.ru

НОЧД и НОНД(задача) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
31.07.2012, 22:49     НОЧД и НОНД(задача) #1
Здравствуйте! Тут на одном сайте задача есть:
Для двух данных натуральных чисел найдите их наибольший четный и наибольший нечетный делители.

Входные данные
Вводятся два натуральных числа, разделенные пробелом. Числа не превосходят 10 в степени 9.

Выходные данные
Выведите два числа через пробел — наибольший общий четный делитель и наибольший общий нечетный делитель. Если какого-то из делителей не существует, выведите вместо него 0.

Ограничения: время работы - не более 1 сек, память не более 64 мб.



Ну так вот, я её решил:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
 
using namespace std;
 
long long first,second,chet=0,nechet=0,temp;
 
long long gcd(long long a, long long b)
{
    while(b)
    {
        a%=b;
        swap(a,b);
    }
    return a;
}
 
int main()
{
    cin>>first>>second;
    temp=gcd(first,second);
    if(temp%2==0)
    {
        chet=temp;
        temp-=1;
        while(temp > 0)
        {
            if(first % temp == 0 && second % temp == 0)
            {
                nechet=temp;
                break;
            }
            temp-=2;
        }
    }
    else
    {
        nechet=temp;
        temp-=1;
        while(temp > 0)
        {
            if(first % temp == 0 && second % temp == 0)
            {
                nechet=temp;
                break;
            }
            temp-=2;
        }
    }
    cout<<chet<<' '<<nechet;
}
Но возникла проблема - на одном из тестов(неизвестно что за тест) программа не проходит по времени, а другие 19 тестов пролетают только в путь, причем очень быстро(0.004 сек самое плохое время).А на этом одном тесте пишет, что более одной секунды(хз сколько, написано только что более 1 сек).


Так вот, уважаемые форумчане-программисты, скажите, в чём дело? Чё не атк в моем решении?

P.S. Прогаю на плюсах не так давно, поэтому скорее всего у меня код быдловатый)))Но на предыдущих задачах(около 20 задач) он очень хорошо работал.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 23:47     НОЧД и НОНД(задача) #2
Смотрите. GE/OCD = greatest even/odd common divisor.

GECD(n, k) = 2 * GCD(n/2, k/2), если n и k чётные
GECD(n, k) = 0 иначе

GOCD(n, k) = GOCD(n, k), если n и k чётные
GOCD(n, k) = GCD(n, k) иначе

Итого:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;
 
int GCD(int a, int b)
{
    if (a < b) {
        swap(a, b);
    }
    while ((b != 0) && (b != 1)) {
        a %= b;
        swap(a, b);
    }
    return (b == 0) ? a : 1;
}
 
int GECD(int a, int b)
{
    if ((a % 2 == 0) && (b % 2 == 0)) {
        return 2 * GCD(a / 2, b / 2);
    }
    else {
        return 0;
    }
}
 
int GOCD(int a, int b)
{
    while ((a % 2 == 0) && (b % 2 == 0)) {
        a /= 2;
        b /= 2;
    }
    return GCD(a, b);
}
 
int main()
{
    int a, b;
    cin >> a >> b;
    cout << GECD(a, b) << " " << GOCD(a, b);
    return 0;
}
Всё так же тормозит?
renald
35 / 35 / 2
Регистрация: 11.02.2012
Сообщений: 105
31.07.2012, 23:49     НОЧД и НОНД(задача) #3
Похоже задача больше математическая, думаю циклы в main лишние
Свойство НОДа: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
Следствие 1: множество общих делителей m, n совпадает с множеством делителей НОД(m, n).

Значит если НОД - нечетный (т.е. на 2 не делится), то четного ОД не существует.
Если НОД - четный, то нечетный нужно искать в цикле пока частное НОД/2 - не будет нечетным

Думаю понятно написал))))
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
01.08.2012, 00:00  [ТС]     НОЧД и НОНД(задача) #4
~OhMyGodSoLong~, ваш проходит!!! Скажите пожалуйста, в чём существенное различие между моим решением и между вашим?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
01.08.2012, 00:20     НОЧД и НОНД(задача) #5
Судя по тому, что оно вылетело по таймлимиту, у вас больно долго вычитается из чисел по одной двойке (циклы 27–35 и 41–49). Это уж больно неэффективный способ найти, например, наибольший общий нечётный делитель каких-нибудь чисел вида 2na и 2nb, где a и b взаимно простые числа (GCD(a, b) = 1), а n в районе так 20. Быстрее сократить эти степени, а потом найти НОД маленьких чисел, а вы же ищете сначала их НОД (который выходит размером в миллион-другой), а потом начинаете мучительно из него вычитать по двойке (выполняя на каждой из полумиллиона итераций два [мееедленных] деления на большие числа), пока не дойдёте до заветной единицы.

Так что существенное различие: мы не перебираем варианты, пока не наткнёмся на подходящее число (тратя O(N) времени), а с помощью свойств функций сводим за O(1) задачу к вычислению НОД, а эта задача вычисляется за O(log N) операций (итого O(log N) времени на всё).
alekola
 Аватар для alekola
21 / 21 / 1
Регистрация: 04.08.2011
Сообщений: 103
01.08.2012, 06:33     НОЧД и НОНД(задача) #6
Напишите пожалуйста адрес сайта, тоже хочу потестироваться
Yandex
Объявления
01.08.2012, 06:33     НОЧД и НОНД(задача)
Ответ Создать тему
Опции темы

Текущее время: 02:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru