anduturacila6's blog

By anduturacila6, history, 3 months ago, In English,

Hello,

I was trying to solve Codeforces Round #489 (Div. 2), problem: (C) Nastya and a Wardrobe,(http://codeforces.com/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.

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Don't divide when doing modulo, instead use https://cp-algorithms.com/algebra/module-inverse.html

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! Yeah, it turned out that the division was the problem. I factored out the two.but thank your for the resource!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a ton. This resource looks damn awesome.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can't divide while using modulo. Instead you have to calculate modulo inverse and multiply it with the answer. And it's equaivalent to (a/b)modulo m when you do (a*modInverse(b, m))modulo m. Read this thread :- http://apps.topcoder.com/forums/?module=Thread&threadID=642253&start=0&mc=10#1110284

And if modulo m is prime, you can directly calculate modInverse(a, m) = (b^(m-2))%m.