algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szybkie potęgowanie modularne - Implementacja w C/C++
Ocena użytkownikóww: *****  / 8
SłabyŚwietny
Nadesłany przez Kamil Dębowski, 06 marca 2011 18:56
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

spm_1_c.cpp:
// Szybkie potegowanie modulo
// www.algorytm.org

#include<cstdio>
#include<conio.h>

int a,b,n;
long long int x,res=1;

int main()
{
	scanf("%d %d %d", &a, &b, &n);
	x=(long long int)a;	// rzutowanie jest konieczne z powodu roznych typow
	do
	{
		x%=(long long int) n;
		if (b&1) // b&1 jest rownowazne czemus takiemu b%2==1, ale jest szybsze i lepiej odpowiada temu co robimy (sprawdzamy najmłodszy bit)
		{
			res*=x;
			res%=(long long int)n;
		}
		x*=x;
	} while (b>>=1);	// b>>=1 jest rownowazne czemus takiemu: b/=2
	printf("%d", (int)res);
	getch();
	return 0;
}
Dodaj komentarz