Тооны зэрэг

Бодлого

A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B<=10^13

Бид энгийн давталт ашиглан үүнийг олж чадна. Өөрөөр хэлбэл A тоог B удаа үржүүлэх ба энэ нь бид 10^13 удаа үржүүлэх хэмжээний зүйлийг ярьж байна. Энэ нь ер нь хэр их үйлдэл вэ? Маш их ба 1 секундэнд 300сая үйлдэл хийдэг гэж төсөөлийлдөө тэгвэл 9 цаг гаруй ажиллахнээ. Бид тооны зэрэг олохын тулд 9 цаг хүлээнэ гэдэг бол тэнэг хүн тэвчээртэй гэдэг шиг л болох нь дээ

Анализ

B зэрэг нь хоёртын бичиглэлдээ $$ \begin{aligned} B = \sum\nolimits_{k=0}^n b_k*2^k \end{aligned} $$

гэж задардаг байг. (b[k] 0 эсвэл 1 байна) Тэгвэл n <= log(10^13) байх юм. Жишээ нь 13 = 1*1 + 0*2 + 1*4 + 1*8 буюу 2тын тооллын системт 1101 гэсэн тоо болохнээ. Бид B тооны хоёртын бичиглэлээр юу хийх вэ гэвэл? Бид A тооны 2^k зэргийг мэддэг гэвэл $$ A^B = \prod\nolimits_{k=0}^n A^{b_k*2^k} $$

болох юм. Ингэснээр бид n үйлдлээр A тооны B зэргийг олж чадаж байна. Учир нь бид дурын A тооны 2^k зэрэгтийг олохын тулд A тооны 2^(k-1) зэргийг мэдэж байхад хангалттай.

Recursive-р төсөөлвөл

Хэрвээ B тоо нь тэгш бол $$ A^B=(A^{B/2})^2 $$ Хэрвээ B тоо сондгой бол $$ A^B=(A^{B/2})^2 * A $$ гэдэг нь тодорхой юм. Эндээс бид A тооны B зэргийг мэдэхийг хүсвэл A тооны B/2 зэргийг мэдэж байхад олж чадна гэдэг нь харагдаж байна. Тэгвэл A тооны B/2 зэргийг олохыг хүсвэл A тооны B/4 зэргийг олоход л хангалттай юм. Энэ мэтчилэн B тоо нь 1 гэсэн тоотой тэнцүү болоход A ба үүнийг бид шууд мэдэж чадна. Одоо бид үүнийг рекурсив ашиглан шийдэж чадна.

Мөн хугацааны үнэлгээ нь log(B) болох ба өмнө нь хэдэн цаг хүлээх байсан бол одоо секунд ч хүрэхгүй бую 10^13 үйлдлийг 43-нхан үйлдэл болгож чадлаа.

Code

// A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B <= 10^13
#include <iostream>
using namespace std;
	
	long long mod = 1e9+7; 
	// 1e9 гэдэг нь 10^9 үржих нь 1 гэсэн утгатай.

long long bodolt1( long long A, long long B ) {
	long long ret = 1, now = A;
	// ret гэдэг хувьсагч нь хариу болох хувьсагч ба анхны утга нь A^0 буюу 1
	// now гэдэг хувьсагч нь A тооны 2^k зэргийн авах ба анхны утга нь 
	// A^(2^0) буюу A байх юм.

	while( B > 0 ) {// Хэрвээ B нь тэгээс их бол хоёртын бичиглэлд нь
			// хөрвүүлж дуусаагүй байна гэсэн үг.

		if( B%2 == 1 ) { // Одоо байгаа B тоо нь 2-т хуваахад 1 үлддэг бол одоо
				 // явж байгаа байрлалдах бит нь 1 байх тул үржвэрт орно.
				 // эсрэг тохиолдолд 0 болох тул өнжиж болно.

			// явж байгаа бит нь 1 тул A тооны одоо явж байгаа тоон зэргээр
			// үржигдэх ёстой гэсэн үг.
			ret = (ret*now)%mod;
		}
		// энэ зэрэг нэгээр ахих буюу квадрат зэрэгт дэвшинэ гэсэн үг юм.
		now = (now*now)%mod;
		B /= 2; // B тоог 2т хувааж битийн байрлал ахина.
	}
	return ret; // хариуг буцааж байна.
}

long long bodolt2( long long A, long long B ) {
	if( B == 0 ) return 1LL; // Хэрвээ B тоо нь 0 бол 1-ыг буцаана. Тооны 0 зэрэг 1
	if( B == 1 ) return A;   // Хэрвээ B тоо нь 1 бол A^1 буюу A тоо өөрөө юм.

	long long ret = bodolt2( A, B/2 );
	// ret хувьсагчийн одоо авж байгаа утга нь A тооны B/2 зэргийг олсон утга юм.
	ret = (ret*ret)%mod;
	// тиймээс үүнийг квадрат зэрэгт дэвшүүлнэ.
	if( B%2 == 1 ) {
		// хэрвээ сондгой бол A тоогоор үржихдэх ёстой.
		ret = (ret*A)%mod;
	}
	return ret; // A^B буцаах
}

int main() {
	long long A, B;
	cin >> A >> B;
	cout << "Bodolt1-> " << bodolt1( A%mod, B ) << endl;
	cout << "Bodolt2-> " << bodolt2( A%mod, B ) << endl;
	return 0;
}

Илүү том тоо болон түүний зэрэг

Дахиад A^B%P буюу A тооны B зэргийг P гэсэн тоонд хуваахад гарах үлдэгдлийг олцгооё(P нь анхны тоо). Өмнө нь бид A,B <= 10^13 гэсэн тохиолдолд бодсон байгаа. Тэгвэл одоо хязгаарлалт маань A, B хоёр тоо нь 10^6 хүртэлх оронтой байж болно. Харин P <= 10^13 гэе.

Fermat-н бага теоремоор $$ A^{P-1}\equiv 1 \mod P $$ Үүнийг ашиглахад энэхүү бодлого амархан болж байгаа (батлахгээд үзээрэй) ба яаж вэ гэвэл $$ A^B\equiv A^{(B \mod P-1)} \mod P $$ болно учир нь A^(P-1) зэрэг бүр 1 болох болхоор B зэргийг олохын тулд тухайн тоо нь P-1-д хуваахад хэд үлдсэн нь л хамаатай юм. Үүнээс бид B тоогоо P-с бага тоо болгож чадлаа.

A тоо маань 10^6 зэрэг хүртэлх оронтой тул бид орон орноор нь л уншиж чадна. (Long long, int төрөлд багтахгүй тул тэмдэгт мөрөөр уншиж байна). Бид A тооны P-д хуваагаад гарсан үлдэгдлийг л сонирхож байгаа тул түүнийг 10-н зэрэгтийн нийлбэрээр бичээд задалж болно $$ A = \sum\nolimits_{k=0}^n (a_k*10^k \mod p) $$ болно энэхүү санааг мөн B тоондээр ашиглаад өмнөх бодлоготой адлиар бодож болно.

#include <bits/stdc++.h> 	// Энэ нь маш олон санг багцалсан сан болно.
							// stdio, math, vector, string ...
using namespace std;
	
	long long mod;

long long solve(long long x, long long y) {
	if(y == 0) return 1;
	if(y == 1) return x%mod;
	long long ret = solve(x, y/2);
	ret = (ret*ret)%mod;
	if( y%2 ) ret = (ret*x)%mod;
	return ret;
}

int main() {
	string x, y; 
	cin >> x >> y >> mod;	//3 тоогоо уншлаа

	long long a = 0, b = 0, now = 1;
	// a-д a%mod хадгална
	// b-д b%mod-1 хадгална
	// now нь 10 зэргийг mod-д модулдсан тоо бөгөөд 
	// анх 10^0 = 1 байна

	for(int i = x.size()-1; i >= 0; i--) {
		a = (a + (x[i] - '0')*now)%mod;
		now = (now*10)%mod;
	}
	
	now = 1;
	for(int i = y.size()-1; i >= 0; i--) {
		b = (b + (y[i] - '0')*now)%(mod-1);
		now = (now*10)%(mod-1);
	}
	
	cout << solve(a, b) << endl;
	return 0;
}

Бүр илүү том тоо

Өнөөх л a^b%mod-оо бодоцгооё. Бид хувиргалт хийгээд a, b < mod болгож чадна. Харин mod <= 10^13 гэвэл a^b бодох явцад үржвэр нь хамгийн ихдээ ойролцоогоор 10^26 болох юм. Гэтэл long long төрөлд үүнийг хийж чадах билүү? Тэгхээр өмнөх бодолтууд зөв биш гэдгийг анзаарсан байх. Үүнийг хэрхэн шийдэх вэ? Үржих үйлдэл нь том тооны хувьд асуудалтай байгаа тул үүнийг зөв олох хэрэгтэй.

x*(y/2)%mod -г мэдэж байхад бид x*y олж чадна. Өмнө нь ашиглаж байсан санаа буюу a^b олсон бодлоготой адил болж байна. Өөрөөр хэлбэл тооны үржвэрийг олохдоо нэмэх үйлдийн тусламжтай олж байгаа ба кодыг нь бичээд үзээрэй.

Заа тэгээд зүгээр л тооны зэрэг боловч ямар түвшинд харахаас хамаараад янз бүрийн асуудал гарж ирж байгаа нь үнэхээр сонирхолтой.