fork(36) download
copy 
  1. # Written by Tacet
  2. def totient(n) :          # n - unsigned int
  3.     result = 1
  4.     p = 2                 #prime numbers - 'iterator'
  5.     while p**2 <= n :
  6.         if(n%p == 0) :    # * (p-1)
  7.             result *= (p-1)
  8.             n /= p
  9.         while(n%p == 0) : # * p^(k-1)
  10.             result *=  p
  11.             n /= p
  12.         p += 1
  13.     if n != 1 :
  14.         result *= (n-1)
  15.     return result
  16.  
  17. def modpow(p, z, b, c, m) : # (p^z)^(b^c) mod m
  18.     if m == 2:
  19.         return p % m
  20.     cp = 0
  21.     while m % p == 0 :
  22.         cp += 1
  23.         m /= p              # m = m' now
  24.     t = totient(m)
  25.     exponent = ((pow(b,c,t)*z)%t + t - (cp%t))%t
  26.                             # exponent = z*(b^c)-cp mod t
  27.     return pow(p, cp)*pow(p, exponent, m)
  28.  
  29. def solve(a,b,c,m) : #split
  30.     result = 1
  31.     p = 2
  32.     while p**2 <= a :
  33.         cp = 0
  34.         while a%p == 0 :
  35.             a /= p
  36.             cp += 1
  37.         if cp != 0 :
  38.            temp =  modpow(p,cp,b,c,m)
  39.            result *= temp
  40.            result %= m
  41.         p += 1
  42.     if a != 1 :
  43.         result *= modpow(a, 1, b, c, m)
  44.     return result % m
  45.  
  46. print solve(5**2 * 97* 7**30 * 2, 9878789, 1214712, 13**2 * 2* 7**8)
  47. # (5^2 * 97* 7^30 * 2)^(9878789^1214712) mod (13**2 * 2* 7**8)
  48. #Silence!
Success #stdin #stdout 0.01s 7852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1671792290
https://ideone.com/bOxFqJ
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!