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

По заданному n необходимо вычислить G - C++

Восстановить пароль Регистрация
 
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
23.05.2012, 19:41     По заданному n необходимо вычислить G #1
...Может показаться простым. По заданному n необходимо вычислить G. Значение G вычисляется следующим образом:
Через GCD(i, j) обозначено наибольший общий делитель целых чисел i и j.
C++
1
2
3
4
5
6
G = 0;
for(i = 1; i < n; i++)
for(j = i + 1;j <= n; j++)
{
    G += GCD(i,j);
}
/*Функция GCD() вычисляет наибольший общий делитель двух чисел*/
Я решил его так:
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
#include <stdio.h>
long gcd( int a, int b )
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}
void recurs()
{   
    __int64 G;
    long n;
        scanf("%ld",&n);
        if (n!=0)
        {
        G=0;
        for(int i=1; i < n;i++)
            for(int j=i+1;j<=n;j++)
                 G+=gcd(i,j);
        printf("%lld\n",G);
        recurs();
        }
}
int main()
{
    recurs();       
}
Но всё выполняется до 3000. потом - не работает. Надо 5 минут ждать для 20000. А мне нужно вычислять до 5000000. Помогите!
пояснение к коду:
Состоит из не более чем 100 строк. Каждая строка содержит целое число n (1 < n < 4000001). Значение n описано выше в условии задачи. Последняя строка содержит n = 0 и не обрабатывается.
Короче по коду будет видно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2012, 19:41     По заданному n необходимо вычислить G
Посмотрите здесь:

C++ По заданному числу n вычислить минимальную сумму чисел
C++ . По заданному вещественному х вычислить значение
По заданному вещественному x вычислить значение C++
Вычисление степени, в которую необходимо возвести 2 для получения числа, которое <= заданному числу C++
Вычислить значение функции по заданному значению переменных: C++
По заданному X рекурсивно вычислить X^2 C++
Вычислить матрицу D по заданному в варианте матричному выражению C++
C++ Вычислить значение функции по заданному алгоритму
C++ По графику функции y=f(x) и заданному вещественному числу a вычислить f(а)
C++ Вычислить первоначальное число, измененное по заданному алгоритму
C++ Вычислить значение k удовлетворяющее заданному условию

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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