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

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

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

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

@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