Пусть дано некоторое (большое) число A и число B. Предположим, что 0<B<10 (случай с другими B я пока не рассмотрел). Нас интересует запись числа A. По определению, запись (если смотреть справа налево), это количество единиц каждого разряда, где разряды (тоже некоторые числа, обозначающие число единиц) начинаются с 1 и каждый раз увеличиваются в O раз, где O называется основанием системы счисления. Число определяется количеством единиц, входящих в него, как сумма количеств каждого разряда, умноженных на «величину» разряда. Ключевое слово — сумма.
Рассмотрим ещё одну лемму.
Лемма 3
Лемма
(A + B) mod C = [(A mod C) + (B mod C)] mod C.
Доказательство:
Пусть A = Z*C + G, B = Y*C + H. Тогда (A + B) mod C = [(Z + Y)*C + (G + H)] mod C = (G + H) mod C.
Таким образом, остаток от даления всего числа A на B есть остаток от деления суммы остатков от деления каждого числа из поразрядных составляющих числа А на B. Цикл служит только для ускорения действия.
Задача:
Дана записть некотрого числа в некоторой системе счисления ( основание которой меньше 11 ) — делимое, некоторое число — делитель, Определить остаток от деления.
bigmod.h
#include <string> #define bigint unsigned long long class BigMod { public: class OutOfRange {}; BigMod(std::string str):delimoe(str),rez(0),osn(-1) {}; void setOsn(int osn); int operator%(int div); private: int osn; bigint rez; std::string delimoe; static bool properOsn(int osn); #ifdef DEBUG void sr(); #endif };
bigmod.cpp
#include <list>
#include «bigmod.h»
#ifdef DEBUG
#include <iostream>
#endif
void
BigMod::setOsn(int c_osn)
{
/*__DOC: Устанавливает систему исчисления */
if ( !properOsn( c_osn ) ) throw OutOfRange();this
->osn = c_osn;
#ifdef DEBUG
std::cout << «Основание установлено = « << this->osn << std::endl;#endif
}
int
BigMod::operator%(int div)
{
if ( !properOsn(osn) ) throw OutOfRange();bool
*A = new bool[div];
memset(A,0,sizeof(bool)*div);/* В массие А значение ИСТИНА элемент A[i] принимает,
* когда такой остаток i уже встречался
*/std::list<int> frc;
/* Список уже встреченных остатков
*//* Вводится вспомогательный массив A,
* чтобы не производить поиск по линейной структуре списка
*/int curOst = 1 % div;
int mult = osn % div;
/* О назначении этой переменной будет сказано несколько позже
*/while(!A[curOst]) {
/* Ищем цикл в последовательности остатков */
A[curOst] = true;frc.push_back(curOst);
curOst = ( curOst * mult ) % div;/* Для того, чтобы не производить пересчёт
* (если в этом вообще есть необходимость)
* величины (A mod B) при переходе от
* (A^i mod B) к (A^(i+1) mod B) используется mult.
*
* При подсчёте выражения для curOst используется
* лемма 1, что позволяет не использовать
* громоздких вычислений величины A^n,
* в том случае, если в последовательности остатков
* долго не возникает цикл
*/
}
/* Теперь в curOst находится остаток, с которого начинается цикл.
*/
#ifdef DEBUG
std::cout << «Последовательность остатков: « << std::endl;for(std::list<int>::const_iterator A = frc.begin(); A != frc.end(); A++) {
std::cout << *A << » «;
}
std::cout << std::endl;#endif
int curPos = delimoe.length()-1;
for( ; *(frc.begin()) != curOst; frc.pop_front()) {/* Обравотка элементов вне цикла
*/
rez += ( delimoe[curPos]-‘0’ )*( *(frc.begin()) ) % div;
—curPos;#ifdef DEBUG
std::cout << «Ациклический элемент « << *(frc.begin()) << » использован и удалён» << std::endl;sr();
#endif
}
for(std::list<int>::const_iterator A = frc.begin() ; curPos>=0; —curPos) {rez += ( delimoe[curPos]-‘0’ )*( *A ) % div;
#ifdef DEBUG
std::cout << «Используется элемент « << *A << std::endl;sr();
#endif
++A;
if(A == frc.end())A = frc.begin();
}
delete[] A;/* Освобождение памяти — наше всё
*/
return rez % div;
}inline bool BigMod::properOsn(int osn)
{/*__DOC: Проверка допустимых значений */
return ( osn > 0 );
}#ifdef DEBUG
inline void BigMod::sr()
{
std::cout << «rez = « << rez << std::endl;
}#endif
Метки: C#, лемма, математика, олимпиады, спортивное программирование, SnarkNews
Август 13, 2008 в 11:28 |
Прошу прощения, в программе была некоторая ошибка с выделением памяти.
Август 14, 2008 в 10:23 |
LOOP
Developer: Ага, вот эти баги! Хотите, я вам покажу особую, отладочную магию?
Bugs: Не-не-не, вротнамноги, остановись, демон, ааа, он меня скукожил, аааргх…
Developer: 0_0
Critical Bug: Эй, хочешь увидеть немного НАСТОЯЩЕЙ магии?
Developer: Эээ, ну давай.
Critical Bug: *SYSTEM CRASH*
Developer: Аааа, фак мой моск, ты чего творишь, я не хочу этого делать, прекрати, ааа…
Critical Bug: 0_0
END LOOP
(взято с http://ibash.org.ru)