Wrong Answer in Modaks inTrinity(TR004)

general
, ,
1

What’s wrong with my solution ?Here’s the link of the problem(link-http://www.codechef.com/TRNT2014/problems/TR004/)

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.math.BigInteger;

import java.util.StringTokenizer;

class Modaks {

/**
 * @param args the command line arguments
 */

public static BigInteger BP(BigInteger A,BigInteger B,BigInteger MOD)
{
    BigInteger R=BigInteger.ONE;
    BigInteger S=A;
    while(B.compareTo(BigInteger.ZERO)>0)
    {
        if((B.mod(new BigInteger("2")).equals(BigInteger.ONE))==true)
        {
            R=R.multiply(S);
            if(R.compareTo(MOD)>0)
                R=R.mod(MOD);
        }
        S=S.multiply(S);
        if(S.compareTo(MOD)>0)
            S=S.mod(MOD);
        
        B=B.shiftRight(1);
    }
    return R;
}
public static void main(String[] args) throws java.lang.Exception 
{
    BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    int T;
    T=Integer.parseInt(br.readLine());
    while(T-->0)
    {
        String str,num = null,num2 = null;
        BigInteger M ;
        BigInteger N ;
        BigInteger MOD=new BigInteger("1000000007");
        str=br.readLine();
        StringTokenizer st=new StringTokenizer(str);
        while(st.hasMoreElements())
        {
            num =(String) st.nextElement();
            num2=(String) st.nextElement();
        }
        N=new BigInteger(num);
        M=new BigInteger(num2);
        BigInteger res=BP(N.mod(MOD),M.mod(MOD),MOD);
        System.out.println(res);
    }
    // TODO code application logic here
}

}

2

coz (a^b)%M is (a%m)^(b%(m-1))

(if a and m are relatively coprime…which indeed are :D)

note the “m-1”

1 Like
3

if no. of drops is 0 , ans would be initial taste level , not 1.

4

@knb_dtu

In problem statement “He wants to earn as much profit as he can. So he has bought a chemical that increases the taste level of the Modaks.”

So if the value of N=0 then answer will be equal to value of TL%MOD.

becuase of this you were getting wrong answer.

1 Like