### anduturacila6's blog

By anduturacila6, history, 3 months ago, ,

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.

•
• +1
•

 » 3 months ago, # |   +1 Don't divide when doing modulo, instead use https://cp-algorithms.com/algebra/module-inverse.html
•  » » 3 months ago, # ^ |   0 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, # ^ |   0 Thanks a ton. This resource looks damn awesome.
 » 3 months ago, # |   0 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#1110284And if modulo m is prime, you can directly calculate modInverse(a, m) = (b^(m-2))%m.
•  » » 3 months ago, # ^ |   0 Thank you so much!