#include<iostream>
using namespace std;
int gcd(int a, int b, int res);
int main()
{
int res = 1;
int n, i, ret;
int count = 1;
cin >> n;
for (i = 2; i < n; i++)
{
ret = gcd(n, i, res);
if (ret == 1)
count++;
}
cout << count;
return 0;
}
int gcd(int a, int b, int res)
{
if (a == b)
return res * a;
else if ((a % 2 == 0) && (b % 2 == 0))
return gcd(a / 2, b / 2, 2 * res);
else if (a % 2 == 0)
return gcd(a / 2, b, res);
else if (b % 2 == 0)
return gcd(a, b / 2, res);
else if (a > b)
return gcd(a - b, b, res);
else
return gcd(a, b - a, res);
}
Please explain what I need to correct like I can use scanf instead of cin?
One more condition is:- The only line of the input is a single integer N which is divisible by no prime number larger than 13. Does that condition affect my TLE ?
Actual question is:
Inverses
Problem Description
Everyone knows about multiplication mod n, where n is a positive integer. The product of two positive integers a and b mod n is the remainder 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 x mod 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 than 1) 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
Constraints
N < 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.
Output
One line containing an integer that gives the number of integers less than N that have a multiplicative inverse
Explanation
Example 1
Input
20
Output
8
Explanation
N=20
If we list the numbers less than 20 which have no common factor with 20 other than 1, they are
1, 3, 7, 9, 11, 13, 17, 19
As there are 8 of them, there are 8 numbers less than 20 which have a multiplicative inverse with respect to 20. Hence the result is 8.
Example 2
Input
36
Output
12
Explanation
N=36. There are 12 numbers less than 36 that have no common factor other than 1 with 36. These are
1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35
Hence, as proved by Euler, there are 12 numbers less than 36 that have a multiplicative inverse with respect to 36. Hence the output is 12.
https://i.stack.imgur.com/cvM0l.png
See Question&Answers more detail:
os