package com.others;

import java.math.BigInteger;

/**
 * We may calculate power with loops, but what if the index is too large ?
 * FastPower aims to calculate quickly in this circumstances with time complexity O(log k),
 * where k is the index.
 *
 */
public class FastPower {
    public static BigInteger calculate(BigInteger n, BigInteger k, BigInteger mod) {
        BigInteger ans = BigInteger.ONE;
        while (!k.equals(BigInteger.ZERO)) {
            int odd = k.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO);
            if (odd > 0) {
                ans = ans.multiply(n).mod(mod);
            }
            k = k.divide(BigInteger.valueOf(2));
            n = n.multiply(n).mod(mod);
        }
        return ans.mod(mod);
    }

    public static long calculate(long n, long k, long mod) {
        long ans = 1;
        while (k != 0) {
            if (k % 2 == 1) {
                ans = (ans * n) % mod;
            }
            k >>= 1;
            n = (n * n) % mod;
        }
        return ans % mod;
    }
}