c++ - Need to improve Running Time Complexity?

Question

#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

Answer 1

First of all, why do you implement your own gcd, when as of C++17<numeric> has std::gcd in it. Your GCD implementation has the same O(log N) complexity, but is quite inefficient due to the big amount of conditionals:

For N=100000000 (100 million) your algorithm runs for 26 seconds on my machine. With std::gcd() the same runs for 15 seconds. This is better but not by much.

If you don't have C++17 then:

int gcd(int a, int b)
{
    if (b < a)
        std::swap(a, b);
    while (a != 0) {
        b %= a;
        std::swap(a, b);
    }
    return b;
}

Gives the same performance as std::gcd().

But that is still too slow. A better way is to work analytically. You want to count the number of integers in the range [1..N] that have no common factors with N. This is trivial to do without actually enumerating all values. First, find all prime factors of N.

Let's say N=a^m * b^n * c^k (for m,n,k >= 1). There are N * (a-1) / a values in the range that don't have a as a factor. Out of these, there are N * (a-1) / a * (b-1) / b that don't have b as a factor, and so on. This works only because a,b,c are prime numbers that are also factors of N. Otherwise the division would not either not be accurate or won't be an integer.

This makes the code blazing fast:

#include<iostream>
int main()
{
    unsigned n;
    std::cin >> n;
    if (!std::cin) {
        std::cout << "Bad input
";
        return 1;
    }
    unsigned count = n;
    unsigned factors_left = n;
    // i is long long to avoid overflow for i * i, 
    // where n is a big prime
    for (unsigned long long i=2 ; i * i <= factors_left ; ++i) {
        if (factors_left % i == 0) {
            while (factors_left % i == 0)
                factors_left /= i;
            count -= count / i;
        }
    }
    if (factors_left > 1)
        // factors_left is a prime number
        count -= count / factors_left;

    std::cout << count << "
";
    return 0;
}

Complexity = O(sqrt(n)). Worst case scenario is when n is prime or a square of a prime. This is much better than the original O(n log n). It takes a fraction of a second to return a result for N=100000000.

edit: If we take into account the additional condition, that the greatest prime factor is 13, then the for loop can iterate until 13. In that case complexity becomes O(log N), since this is the complexity of the inner loop.