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

Popular posts from this blog

Hackerrank - Quicksort 2 - Sorting

Hackerrank - Day of the Programmer

Hackerrank - UNIQUE ARMSTRONG NUMBER