Перевод кода с Java

@Севак · Регистрация: 25.09.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте! Есть код на java, который работает недостаточно быстро, для его ускорения решил переписать его на c++, вот что вышло, помогите исправить реализацию на c++ или укажите на ошибки, буду благодарен!

Java
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
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    public static final BigInteger one = BigInteger.ONE;
    public static final BigInteger minusOne = BigInteger.valueOf(-1);
    public static final BigInteger two = BigInteger.valueOf(2);
    public static final BigInteger three = BigInteger.valueOf(3);
    public static final BigInteger mod = BigInteger.valueOf(1000000007);
 
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        System.out.println(G(n));
    }
 
    public static BigInteger G(int n) {
        if(n % 2 == 0) {
            return two.shiftLeft(n).add(one).divide(three).mod(mod).subtract(one);
        } else {
            return two.shiftLeft(n).add(minusOne).divide(three).mod(mod);
        }
    }
 
}

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
#include <iostream>
#include <stdint.h>
#include <math.h>
 
using namespace std;
 
int64_t G(int64_t n, int64_t mod) {
    if(n % 2 == 0) {
        return (((2 << n) + 1)/3) % mod - 1;
    } else {
        return (((2 << n) - 1)/3) % mod;
    }
}
 
 
int main() {
    int64_t n;
    int64_t mod = 1000000007;
 
    cin >> n;
    cout << G(n, mod);
 
    return 0;
}

@Dani · 06.07.2013, 20:47

Это ж одно и тоже, нет?

@Севак · 06.07.2013, 20:48 **[ТС]**

p.s.: 1 <= n <= 1_000_000_000
в реализации c++ на больших числах выдает 0

Добавлено через 26 секунд
Dani, я знаю, но работает некорректно

@Dani · 06.07.2013, 20:52

Не по теме:

Сообщение от Севак

Dani, я знаю, но работает некорректно

нет, здесь был один и тот же код на Java и там и там.

@Севак · 06.07.2013, 20:53 **[ТС]**

Dani,

Не по теме:

сначала нечаянно не то вставил

@Thinker · 06.07.2013, 21:14

Сообщение от Севак

p.s.: 1 <= n <= 1_000_000_000
в реализации c++ на больших числах выдает 0

так и должно быть, $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{1\,000\,000\,000}$ ни в один тип данных не влезет, вот и получаете нули, n не может превышать значения 62, так как там еще 2-ка есть

@gray_fox · 06.07.2013, 21:15

Сообщение от Севак

p.s.: 1 <= n <= 1_000_000_000

С помощью int64 2^10⁹ конечно не представишь

@Севак · 06.07.2013, 21:18 **[ТС]**

Всем спасибо, буду думать дальше!

@Belfegor · 06.07.2013, 21:20

Не по теме:

в с++ нет готового типа, надо писать с длинной арифметикой

@Thinker · 06.07.2013, 21:24

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

@Dani · 06.07.2013, 21:27

Тут явно: обычная длинка + двоичное возведение в степень

Добавлено через 1 минуту
Возведение в степень будет за логарифм, итого 31 перемножение.

@Thinker · 06.07.2013, 21:30

Сообщение от Dani

Возведение в степень будет за логарифм, итого 31 перемножение.

Не по теме:

это все понятно, только в десятичный вид перевести все это не так просто. это для задачи из другой ветки

@Севак · 06.07.2013, 21:32 **[ТС]**

насчет двоичного возведения в степень:
правильно ли я помню что 2^n == 1 и n нулей?
вот еще на что наткнулся

@Thinker · 06.07.2013, 21:33

Сообщение от Севак

насчет двоичного возведения в степень:
правильно ли я помню что 2^n == 1 и n нулей?

правильно

@Dani · 06.07.2013, 21:35

Thinker, что? переводить не нужно ничего.

@Thinker · 06.07.2013, 21:37

Сообщение от Dani

Thinker, что? переводить не нужно ничего.

я про эту задачу
Возведение двойки в миллиардную степень
немного похожая задача

@Dani · 06.07.2013, 21:39

Двоичное возведение в степень строится по следующему принципу. Есть функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b)$ , если b - четное, то из числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b)$ можно извлечь корень, получается, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = {(power(a, b/2))}^{2}$ . Если же b нечетное, то $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = power(a, b-1) * a$ . При b = 1 , результат равен a.

Ничего кроме умножения и рекурсивного спуска.

@Thinker · 06.07.2013, 21:42

Dani, это да, очень даже понятно

но та задача даже так быстро не решается. я там оценил время работы алгоритма. если использовать двоичное возведение, то оно даст выигрыш не более чем в 10 раз и время работы будет сутками исчисляться

@Dani · 06.07.2013, 21:45

Хм... щас... может Карацуба
http://www.wolframalpha.com/in... 1000000000

@Thinker · 06.07.2013, 21:46

Сообщение от Dani

Хм... щас... может Карацуба

умножение по методу Карацубы тоже хорошо известная и полезная вещь, но увы...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.07.2013, 20:47
	Это ж одно и тоже, нет? 0

@Севак любитель покушать 687 / 641 / 248 Регистрация: 25.09.2011 Сообщений: 1,313
	06.07.2013, 20:48 [ТС]
	p.s.: 1 <= n <= 1_000_000_000 в реализации c++ на больших числах выдает 0 Добавлено через 26 секунд Dani, я знаю, но работает некорректно 0

@Севак любитель покушать 687 / 641 / 248 Регистрация: 25.09.2011 Сообщений: 1,313
	06.07.2013, 20:53 [ТС]
	Dani, Не по теме: сначала нечаянно не то вставил 0

@Севак любитель покушать 687 / 641 / 248 Регистрация: 25.09.2011 Сообщений: 1,313
	06.07.2013, 21:18 [ТС]
	Всем спасибо, буду думать дальше! 0

@Belfegor
	06.07.2013, 21:20
	Не по теме: в с++ нет готового типа, надо писать с длинной арифметикой 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	06.07.2013, 21:24
	да, только длинная арифметика должна быть очень продуманной, а то возникнет такая же проблема, как здесь Возведение двойки в миллиардную степень 1

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.07.2013, 21:27
	Тут явно: обычная длинка + двоичное возведение в степень Добавлено через 1 минуту Возведение в степень будет за логарифм, итого 31 перемножение. 1

@Севак любитель покушать 687 / 641 / 248 Регистрация: 25.09.2011 Сообщений: 1,313
	06.07.2013, 21:32 [ТС]
	насчет двоичного возведения в степень: правильно ли я помню что 2^n == 1 и n нулей? вот еще на что наткнулся 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.07.2013, 21:35
	Thinker, что? переводить не нужно ничего. 1

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.07.2013, 21:39
	Двоичное возведение в степень строится по следующему принципу. Есть функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b)$ , если b - четное, то из числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b)$ можно извлечь корень, получается, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = {(power(a, b/2))}^{2}$ . Если же b нечетное, то $https://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = power(a, b-1) * a$ . При b = 1 , результат равен a. Ничего кроме умножения и рекурсивного спуска. 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	06.07.2013, 21:42
	Dani, это да, очень даже понятно но та задача даже так быстро не решается. я там оценил время работы алгоритма. если использовать двоичное возведение, то оно даст выигрыш не более чем в 10 раз и время работы будет сутками исчисляться 1

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.07.2013, 21:45
	Хм... щас... может Карацуба http://www.wolframalpha.com/in... 1000000000 2