From anonymous, 2 Months ago, written in Cuesheet.
Embed
  1. class Cls {
  2.     int modpow(int x, int m, int n) {
  3.         if (n == 0) { return 1; }
  4.         if (n == 1) { return x; }
  5.         if (n%2 == 0) { return modpow(x*(x%m),n/2,m)%m; }
  6.         if (n%2 == 1) { return (x *  modpow(x*(x%m),(n-1)/2,m)%m )%m; }
  7.     }
  8.  
  9.     void Main() {
  10.         int x;
  11.         int n;
  12.         int m;
  13.  
  14.         WriteString("x? ");
  15.         x = ReadInt();
  16.         WriteString("n? ");
  17.         n = ReadInt();
  18.         WriteString("m? ");
  19.         m = ReadInt();
  20.  
  21.         WriteInt(modpow(x, n, m));
  22.         WriteString("");
  23.  
  24.         // z.B. mit x=3, n=2, m=2:
  25.         // 3 ^ 2 mod 2
  26.         // expected: 1
  27.         // actual: 0
  28.     }
  29. }
  30.