Inverses - codevita
Everyone knows about multiplication mod n, where n is a positive integer. The product of two positive integers a and b mod n is theremainder when the product is divided by n.A number a is said to have a multiplicative inverse with respect to n if there is a positive integer x less than n so that the product of a and xmod n is 1
The great mathematician Euler proved that every positive integers less than n that is prime to n (has no common factor with n other than1) has a multiplicative inverse with respect to n.This problem is to find the number of positive integers less than n that have a multiplicative inverse with respect to n
ConstraintsN < 10^9
Input Format;
The only line of the input is a single integer N which is divisible by no prime number larger than 13
import java.util.Scanner;
public class Inverse {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
Integer[] primeNos = {2,3,5,7,11,13};
for (int i = 0; i < primeNos.length; i++) {
if(num%primeNos[i] == 0){
num = num-(num/primeNos[i]);
}
}
System.out.println(num);
}
}
Comments
Post a Comment