Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Класс для строк. Реализация, сравнивание, копирование, конкатенация http://www.cyberforum.ru/cpp-beginners/thread584560.html
Помогите пожалуйста создать класс для строк. Реализация, сравнивание, копирование, конкатенация. Через указатели и массивы символов. String использовать нельзя.
C++ Классы и основы наследования, с++ Последняя лабораторная работа семестра. Немаленькая...про классы мало что знаю. Сложно ли это сделать? Не могли бы помочь ? 1. Разработайте класс GeometricalBody (геометрическое тело), который... http://www.cyberforum.ru/cpp-beginners/thread584557.html
ошибка в передаче значений MPI функций C++
Добрый вечер. Не силен в MPI, собственно поэтому пишу Вам. Нужно со всех процессов кроме нулевого отправить самое минимальное значение нулевому процессу. Пробовал через MPI REDUCE и MPI MIN,...
Двусвязный кольцевой список, файлы и сортировка C++
Здравствуйте! Нужна помощь со списками, мне нужно чтобы он не только создавался, но и в файл записывался и считывался оттуда в функциях BuiltRing и VyvodLeftRight. А в InsAfter и Delete нужно...
C++ Дан двумерный массив размерностью 5х6, заполненный целыми числами с клавиатуры http://www.cyberforum.ru/cpp-beginners/thread584533.html
Дан двумерный массив размерностью 5х6, заполненный целыми числами с клавиатуры. Сформировать одномерный массив, каждый эле¬мент которого равен наибольшему по модулю элементу соответствующего столбца.
C++ Даны натуральное число n, действительные числа a1, …, an. Получить: min(a1, a3, …) Задача:Даны натуральное число n, действительные числа a1, …, an. Получить: min(a1, a3, …) #include<iostream> using namespace std; int main() { const int n=5; double x, min; int i; ... подробнее

Показать сообщение отдельно
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1

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

23.05.2012, 19:41. Просмотров 346. Ответов 0
Метки (Все метки)

...Может показаться простым. По заданному 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 и не обрабатывается.
Короче по коду будет видно.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.