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

Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Конструктор/деструктор http://www.cyberforum.ru/cpp-beginners/thread806865.html
Подскажите пожалуйста как внедрить в вот эту программу конструктор и деструктор... В программе есть базовый класс (летательные аппараты) и два производных. #include "stdafx.h" #include <stdio.h>...
C++ Составить программу формирования рабочего файла(бинарного файла из структур) на основе исходного текстового файла (а)Составить программу формирования рабочего файла(бинарного файла из структур) на основе исходного текстового файла; (б)Составить программу сбора и печати сведений в указанном формате по данным... http://www.cyberforum.ru/cpp-beginners/thread806864.html
ошибка компиляции C++
Задача Даны действительная матрица размера действительные числа , натуральные числа р, q . Образовать новую матрицу размера вставкой после строки с номером р данной матрицы новой строки с...
Файловый ввод-вывод C++
Дан текстовый файл с некоторыми целыми числами. Открыть файл, определить максимальное значение элементов. Если оно кратно трем, заменить каждое третье значение файла нулем, если кратно пяти –...
C++ проверьте, пожалуйста, код. Перемножение степенных рядов http://www.cyberforum.ru/cpp-beginners/thread806825.html
#include "stdafx.h" #include <iostream> using namespace std; float* vvod (int n) { setlocale(LC_ALL, "rus"); float* mas = new float ; for (int i = 0; i <= n; ++i) {
C++ Перегрузка оператора [] У меня есть класс Przedzial (Интервал) с приватными переменными double low и double up И нужно перегрузить оператор для случая ob , где ob - объект класса m - на сколько кусков делим интервал ... подробнее

Показать сообщение отдельно
roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88

Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" - C++

12.03.2013, 20:58. Просмотров 1458. Ответов 4
Метки (Все метки)

Нужно максимально быстро посчитать A^B mod C. Написала алгоритм, казалось бы все хорошо, да вот только сижу я на e-olimp'e, делаю задачки, а ему не нравится. Последние несколько тестов не проходит, пишет "неправильный ответ". Из-за чего это может быть? Выхожу за границы __int64? Подскажите, мальчики, пожалуйста. Вот моя реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int main()
{
   unsigned __int64 a, b, c;
 
   while(scanf("%I64d %I64d %I64d", &a, &b, &c) == 3)
   {
       unsigned __int64 r = 1;
 
       while(b != 0)
       {
           if(b%2 != 0) r = (r * a)%c;
           b /= 2;
           a = (a * a) % c;
       }
 
       printf("%I64d\n", r);
   }
   return 0;
} //main
Для написания этой программы использовала "алгоритм русского крестьянина" а также известный факт о том, что http://www.cyberforum.ru/cgi-bin/latex.cgi?(A * B) mod C = ((A mod C) * (B mod C) ) mod C
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.