Ocena użytkownikóww: ***** / 3
Nadesłany przez Tomasz Lubiński, 13 listopada 2006 01:00
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_cs/SPM.cs:
//
// Szybkie Potegowanie modulo
//
// www.algorytm.org
// (c)2007 Tomasz Lubinski
//
using System;
namespace spm_cs
{
/// <summary>
/// Szybkie Potegowanie modulo
/// </summary>
class SPM
{
/// <summary>
/// Calculates a^b mod m
/// </summary>
/// <param name="a">a</param>
/// <param name="b">b</param>
/// <param name="m">m</param>
/// <returns>a^b mod m</returns>
public static int power_modulo_fast(int a, int b, int m)
{
int i;
long result = 1;
long x = a%m;
for (i=1; i<=b; i<<=1)
{
x %= m;
if ((b&i) != 0)
{
result *= x;
result %= m;
}
x *= x;
}
return (int)result;
}
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
//9688563^45896 mod 71 = 30
Console.WriteLine("9688563^458926 mod 71 = " + power_modulo_fast(9688563, 458926, 71));
//12^53 mod 7 = 3
Console.WriteLine("12^53 mod 7 = " + power_modulo_fast(12, 53, 7));
}
}
}