Question Concerning Working With Modulo and BIg Numbers

Revision en1, by anduturacila6, 2018-06-22 02:50:04

Hello,

I was trying to solve Codeforces Round #489 (Div. 2), problem: (C) Nastya and a Wardrobe,(http://codeforces.net/contest/992/problem/C), and my solution so far gets the first 21 test cases right.

I know how to solve it, the only problem is outputting correctly using modulo.

My code currently looks like this:

import java.io.*;
import java.util.*;

public class Main {

    public static int MOD = (int)Math.pow(10, 9)+7;


    public static long powMod(long X,long N){
        long result = 1;
        X = X % MOD;
        while(N > 0){
            if(N % 2 == 1)
                result = (result * X) % MOD;
            N >>= 1;
            X = (X*X)%MOD;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        long X = in.nextLong();
        long K = in.nextLong();
        if(X == 1)
            System.out.println(powMod(2, K) + 1);
        else if(X == 0)
            System.out.println(0);
        else if(K == 0)
            System.out.println(X*2);
        else {
            long upperLimit = ((X%MOD) * powMod(2, K + 1));
            long diff = (X - 1) % MOD;
            long lowerLimit = (2*((-diff*((1-powMod(2, K)))) + (X%MOD)))%MOD;
            if(X < 1000 && X > 100)
                lowerLimit = (2*((-diff*((1-powMod(2, K)))) + (X%MOD)));


            if(X > 1000 && K < 1000)
                System.out.println((((upperLimit + lowerLimit)%MOD) / 2) % MOD);
            else
                System.out.println(((upperLimit + lowerLimit) / 2) % MOD);
        }

    }
}

I've tried several different combinations of modulo addition and multiplication, but none seem to reliably output the answer without me cheating a bit by adding if conditions.

I've seen the rules for modulo arithmetic and multiplication, but following those rules seems to get me even more qrong answers.

I was wondering what exactly am I doing wrong concerning the use of modulo and what to keep in my mind when I encounter similar problems.

Tags ask a question, modulo multiplication, modulo

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English anduturacila6 2018-06-22 02:50:04 2163 Initial revision (published)