Перевод кода с 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

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

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

Новые блоги и статьи Все статьи Все блоги /
WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Old Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .

@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