Применение лемм 1 и 2

Пусть дано некоторое (большое) число 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