user123 user123 - 2 months ago 6
C Question

which data type to use in C and Java for calculating the modulo inverse of a number?

I went through the below mentioned tutorial and I tried calculating the modulo inverse of the number in C as well as in Java but in both cases , I am getting the output as 0 ,please guide me in my correcting my code .

https://www.hackerearth.com/practice/math/number-theory/multiplicative-inverse/tutorial/

import java.lang.Math;
import java.util.*;
import java.math.BigInteger;
import java.math.BigDecimal;
class TestClass {
public static void main(String args[] ) throws Exception {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
BigInteger bi=BigInteger.valueOf(a);
BigInteger k = new BigDecimal(Math.pow(10,9)).toBigInteger();
BigInteger b=k.add(BigInteger.valueOf(7));
BigInteger c=b.subtract(BigInteger.valueOf(2));
BigInteger m=bi.modPow(c,BigInteger.valueOf(1));
BigInteger d=m.mod(b);
System.out.println(d);

}
}


In C ,

#include <stdio.h>
#include<inttypes.h>
#include<math.h>
int main()
{
uintmax_t a;
scanf(" %ju",&a);
uintmax_t b=pow(10,9);
uintmax_t m=b+7;
uintmax_t c=((uintmax_t)pow(a,m-2))%(m);
printf("%ju",c);
return 0;
}


I am unable to get the reason behind the overflow here ,please clarify this .

Answer

The reason your java code does not work is that

BigInteger m=bi.modPow(c,BigInteger.valueOf(1));

calculates bi^c mod 1, which is 0 for any bi and c.

What you want to calculate is bi^c mod b, which is coded as

BigInteger m = bi.modPow(c, b);