CODEWITHSUNDEEP
javamoduloexponentiation
Shubham44
Shubham44

Reputation: 11

How to calculate (a^b^c^d) mod 10^9+7?

i tried using this.

import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static void main (String[] args) {
        Scanner s=new Scanner(System.in);
            int m=1000000007;
            int a=s.nextInt();
            int b=s.nextInt();
            int c=s.nextInt();
            int d=s.nextInt();
            long temp1=power(c,d)%m;
            long temp2= power(b,temp1)%m;
            long result=power(a,temp2)%m;
            System.out.println(result);
    }
    public static long power(int x, long n){
        int m=1000000007;
        if(n==0){
            return 1;
        }
        if(n==1){
            return x;
        }
        if(n%2==0){
            return (power(x,n/2)*power(x,n/2))%m;
        }else {
            return ((power(x,n/2)*power(x,n/2))%m * x)%m;
        }
    }
}

but problem is when i increase size of a b c d then its showing TLE. like for a=2 b=2 c=2 d=2 its giving output 65536 but when i take a=12 b=12 c=12 d=12 output should be 322269119 but using this it is showing Time limit exceed error. anyone can explain how to do this type of qurstion where it said that output value will be large so print is after doing mod 10^9+7. Edit: a b c d values can be different.

Upvotes: 0

Views: 177

Answers (1)

user555045
user555045

Reputation: 64904

The TLE is due to power recursively calling itself twice per invocation, so it expands to a full binary tree of calls (size: n) instead of into a nice linear chain of calls (length: log(n)) which is how Exponentiation by Squaring is supposed to work. In other words, it's exponentially slower than it needs to be, and for a very boring reason. Easy fix:

public static long power(int x, long n){
    int m=1000000007;
    if(n==0){
        return 1;
    }
    if(n==1){
        return x;
    }
    long p = power(x,n/2);
    if(n%2==0){
        return p * p % m;
    }else {
        return (p * p % m) * x % m;
    }
}

But there is also a "math bug" in your program: abcd mod n is not equivalent to a^(b^(c^d mod n) mod n) mod n. Modular addition and multiplication work that way, but exponentiation has a different kind of periodicity.

Just using big integers naively is not sufficient, 12^12^12 would be a 4TB BigInteger, even on a computer that could handle that, computing or using such a physically large number would just take too long. But you can use Euler's theorem, and compute 12^12^12 mod φ(n). 12^12 is no big deal it even fits in a long, then 12 to the power of that long can be a modexp again but modulo φ(1E9+7) which is 1E9+6. For slightly larger c and d, c^d can also be computed as a BigInteger, as long as it isn't too big.

When c or d are so large that c^d is a problem even with BigIntegers, you can use more tricks to compute b^c^d mod φ(n) without the "full" c^d. Unfortunately Euler's theorem is not applicable to the "inner" exponentiation because the GCD of the modulus and the base may not be 1 (and isn't 1 in the example with the twelves), but there is a more complex expression that works in that case.

Upvotes: 1

Related Questions