1. import scala.collection.mutable.{Map => MMap}
  2. import scala.collection.mutable.{Set => MSet}
  4. object Wrapper {
  5. val Array(cardPubKey, doorPubKey) = scala.io.Source.fromFile("input").getLines.toArray.map(BigInt.apply)
  6. val M = 20201227
  7. val one = bi("1")
  8. val seven = bi("7")
  10. def bi(s: String) = BigInt(s)
  12. def powMod(subject: BigInt, n : Int):BigInt = n match {
  13. case 0 => one
  14. case 1 => subject.mod(M)
  15. case n => if(n%2 == 0) {
  16. val half = powMod(subject, n/2).mod(M)
  17. (half*half).mod(M)
  18. } else {
  19. val half = powMod(subject, n/2).mod(M)
  20. (half*half*subject).mod(M)
  21. }
  22. }
  24. def search(target: BigInt): Int = {
  25. var loop=0
  26. var check = powMod(seven, loop)
  27. while(check != target){
  28. loop += 1
  29. check = powMod(seven, loop)
  30. }
  31. loop
  32. }
  34. def solve() = {
  35. println(cardPubKey, doorPubKey)
  36. val cardLoop = search(cardPubKey)
  37. val doorLoop = search(doorPubKey)
  39. println(powMod(doorPubKey, cardLoop))
  40. println(powMod(cardPubKey, doorLoop))
  41. }
  43. }
  44. Wrapper.solve()