Given integers C and N, (c <= n <= 10^9), find the amount of pairs i,j (n >= i >= j >= 1), where gcd(i,j) == C

Question

Given integers C and N, (c <= n <= 10^9), find the amount of pairs i,j (n >= i >= j >= 1), where gcd(i,j) == C

long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void solve(int tt){
    int c,n;
    cin >> c >> n;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            if(gcd(i,j) == c) ans++;
        }
    }
    cout << ans;
    return;
}

This is getting timed out and I've tried various different ways to try and fix it - nothing is working... Does anyone know the code to optimize this? (Output %100000007)

Answer 1

"Given integers C and N, (c <= n <= 10^9), find the amount of pairs i,j (n >= i >= j >= 1), where gcd(i,j) == C"

We can divide everything by C to get:

How many integers i and j satisfy: 2 <= j < i <= n/c, and are relatively prime?

Let's check a few:

n/c   count (new pairs listed in parens)
<=2   0
3     1  (2,3) 
4     2  (3,4)
5     5  (2,5), (3,5), (4,5)
6     6  (5,6)
7     11 (2,7), (3,7), (4,7), (5,7), (6,7)
8     14 (3,8), (5,8), (7,8)
9     19 (2,9), (4,9), (5,9), (7,9), (8,9)

Each time we increment i, we can pair it with all smaller values of j >= 2 that don't have any of the same factors. For primes this is all smaller values of j >= 2.

This is https://oeis.org/A015613.

Here's an approach courtesy of geeksforgeeks:

Find the count of smaller integers >= 2 relatively prime to n, also known as Euler's totient function, in O(sqrt(n) * log(n)) time as follows:

1) Initialize result as n
2) Consider every number 'p' (where 'p' varies from 2 to Φn). 
   If p divides n, then do following
   a) Subtract all multiples of p from 1 to n [all multiples of p
      will have gcd more than 1 (at least p) with n]
   b) Update n by repeatedly dividing it by p.
3) If the reduced n is more than 1, then remove all multiples
   of n from result.

Add these up for 2 through n in O((n^1.5) * log(n)) time.