fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.HashMap;
  6. import java.util.List;
  7. import java.util.Map;
  8.  
  9.  
  10. class OldSolution {
  11.     static long a, n, m, base10, base10n, base10Mod, rPowN;
  12.     static long totient;
  13.     static Map<Long, Long> reuseTotients = new HashMap<>();
  14.     static List<Long> primes = new ArrayList<>();
  15.  
  16.     public static long gcd(long a, long b) {
  17.         if (a == 0)
  18.             return b;
  19.         return gcd(b % a, a);
  20.     }
  21.  
  22.     public static boolean testPrime(long t) {
  23.         long tsqrt = (long) Math.sqrt(t);
  24.         long prime;
  25.         for (int i = 0; i < primes.size(); ++i) {
  26.             prime = primes.get(i);
  27.             if (prime > tsqrt) {
  28.                 break;
  29.             }
  30.             if (t % prime == 0) {
  31.                 return false;
  32.             }
  33.         }
  34.         return true;
  35.     }
  36.  
  37.     public static void calcPrimes(long n) {
  38.         long lastPrime = primes.get(primes.size() - 1);
  39.         long i = lastPrime / 6 + 1;
  40.         long a, b;
  41.  
  42.         if (lastPrime % 6 == 5) {
  43.             if (testPrime(6 * i + 1)) {
  44.                 primes.add(6 * i + 1);
  45.             }
  46.             i++;
  47.         }
  48.  
  49.         while (true) {
  50.             a = 6 * i - 1;
  51.             b = 6 * i + 1;
  52.             if (testPrime(a)) {
  53.                 primes.add(a);
  54.             }
  55.             if (testPrime(b)) {
  56.                 primes.add(b);
  57.             }
  58.  
  59.             if (b > n) {
  60.                 break;
  61.             }
  62.             i++;
  63.         }
  64.  
  65.     }
  66.  
  67.     public static void calcTotient() {
  68.         if (reuseTotients.containsKey(m)) {
  69.             totient = reuseTotients.get(m);
  70.         }
  71.         if (primes.get(primes.size() - 1) < m) {
  72.             calcPrimes(m);
  73.         }
  74.         int i = 0;
  75.         for (; primes.get(i) < m; ++i) ;
  76.         totient = i;
  77.         reuseTotients.put(m, totient);
  78.     }
  79.  
  80.     public static void getBase10() {
  81.         //use a
  82.         long a1 = a;
  83.         long t = 0;
  84.         base10 = 1;
  85.         while (a1 > 0) {
  86.             a1 /= 10;
  87.             t++;
  88.             base10 *= 10;
  89.         }
  90.         base10n = t;
  91.     }
  92.  
  93.     public static long calcRpowN(long n1) {
  94.         if (base10Mod == 1) {
  95.             return 1;
  96.         }
  97.         long rPowN = 1;
  98.         long temp = base10Mod;
  99.         long i = 1;
  100.         while (n1 != 0) {
  101.             if ((n1 & i) != 0) {
  102.                 rPowN = (rPowN * temp) % m;
  103.                 n1 ^= i; //unset ith bit
  104.             }
  105.             i <<= 1;
  106.             temp = ((temp * temp) % m);
  107.         }
  108.         return rPowN;
  109.     }
  110.  
  111.     public static void calcBase10Mod() {
  112.         getBase10();
  113.         //calc base10mod first
  114.         base10Mod = base10 % m;
  115.         if (base10Mod == 1) {
  116.             return;
  117.         }
  118.  
  119.         // calc rPowN
  120.         // to use euclid's method, we need 10^t and m to be coprimes
  121.         if (m % 5 != 0 && m % 2 != 0) {
  122.             //co prime here
  123.             calcTotient();
  124.             long n1 = n % totient;
  125.             rPowN = calcRpowN(n1);
  126.         } else {
  127.             rPowN = calcRpowN(n);
  128.         }
  129.     }
  130.  
  131.  
  132.     public static long modInverseFast(long a, long m) {
  133.         long m0 = m, temp, q;
  134.         long x0 = 0, x1 = 1;
  135.  
  136.         if (m == 1)
  137.             return 0;
  138.  
  139.         while (a > 1) {
  140.             // floor it
  141.             q = a / m;
  142.  
  143.             temp = m;
  144.             m = a % m;
  145.             a = temp;
  146.  
  147.             temp = x0;
  148.             x0 = x1 - q * x0;
  149.             x1 = temp;
  150.         }
  151.  
  152.         // Make x1 positive
  153.         if (x1 < 0)
  154.             x1 += m0;
  155.  
  156.         return x1;
  157.     }
  158.  
  159.     public static long getMultiModInverse(long x, long m) {
  160.         if (gcd(x, m) == 1) {
  161.             return modInverseFast(x, m);
  162.         }
  163.         x = x % m;
  164.         for (long i = 1; i < m; ++i) {
  165.             if ((x * i) % m == 1)
  166.                 return i;
  167.         }
  168.  
  169.         return -1;
  170.     }
  171.  
  172.  
  173.     public static void main(String[] args) throws IOException {
  174.         primes.add(2l);
  175.         primes.add(3l);
  176.         primes.add(5l);
  177.  
  178.         long ans;
  179.  
  180.  
  181.         final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  182.         final StringBuilder stringBuilder = new StringBuilder();
  183.  
  184.         for (int t = Integer.parseInt(br.readLine()); t > 0; t--) {
  185.             final String split[] = br.readLine().split(" ");
  186.             a = Long.parseLong(split[0]);
  187.             n = Long.parseLong(split[1]);
  188.             m = Long.parseLong(split[2]);
  189.  
  190.  
  191.             calcBase10Mod();
  192.             if (base10Mod == 1) {
  193.                 ans = ((a % m) * (n % m)) % m;
  194.                 stringBuilder.append(ans).append('\n');
  195.                 continue;
  196.             }
  197.  
  198.             long numer = (rPowN - 1 + m) % m;
  199.             numer = (numer * (a % m)) % m;
  200.  
  201.             // calc r-1 mod m
  202.             long denInverse = getMultiModInverse(base10 - 1, m);
  203.             ans = (numer * denInverse) % m;
  204.             stringBuilder.append(ans).append('\n');
  205.  
  206.  
  207.         }
  208.  
  209.         System.out.println(stringBuilder);
  210.  
  211.     }
  212. }
  213.  
Success #stdin #stdout 0.07s 54912KB
comments (?)
stdin
copy 
5
12 2 17
12 2 7
523 3 11
0 3 11
523 3 999
stdout
copy 
5
1
6
0
570
https://ideone.com/cPPUEI
language:
Java (HotSpot 12)
created:
1 day 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!