solution of spoj NAJPWG. Gives TLE

Question

Link to the question is - spoj question

I have tried solving the question by this approach - The number of pairs in N range = Number of pairs in N-1 range + some new pairs.

But I don't know what else optimisation should be done here to avoid TLE. I also read about euler totient function but couldn't really understand the approach. I've read 4 ways to calculate euler phi but all require the same O(n^2), I guess.

P.S - I would just like to know hints regarding what should be the approach further and not the direct solution. Hints will do. Thanks a lot in advance.

My code to this question is -

#include<stdio.h>
typedef unsigned long long int ull;
ull a[100000] = {0};

inline ull g()
{
    ull n=0;
    char ch;
    ch = getchar_unlocked();
    while(ch < '0' || ch > '9')
        ch = getchar_unlocked();
    while(ch >= '0' && ch <= '9') {
        n = (n<<3) + (n<<1) + (ch - '0');
        ch = getchar_unlocked();
    }
    return n;
}

ull gcd( ull a , ull b)
{
    if(b == 0)
        return a;
    else 
        return gcd(b , a % b);
}

ull find(ull n)
{
    if(n == 0 || n == 1)
        return n;
    else if(a[n] != 0)
        return n;
    else
        return find(n-1);
}

ull range(ull n)
{
    ull c, i, nf,t;
    nf = find(n);
    c = a[nf];
    t = nf;
    nf++;
    while(nf <= n) {
        a[nf] = a[t];
        for(i = 2 ; i <= nf ; i++) {
            ull gd = gcd(i,nf);
            if(gd > 1) {
                c++;
                a[nf]++;
            }
        }
        nf++;
    }
    return c;
}

int main()
{
    ull t = g();
    ull i = 1;
    while(t--) {
        ull n = g();
        if(a[n] == 0)
            a[n] = range(n);
        printf("Case %llu: %llu\n",i++,a[n]);
    }   
    return 0;
}

Answer 1

Just go have a try and got AC.

As you said hints only, here's some based on my AC solution and your attempt:

1. Phi function is O(n^2)? really? At least in my code, I do not think it is O(n^2)
2. GCD function is not needed
3. It is a simple math / number theory problem, not a DP problem
4. Precompute, precompute, precompute! You can precompute so many things, such that loop for each input n, you can just output answer in O(1)!
5. Learn Prime Sieve & Fundamental theorem of arithmetic first before you look into Phi function. (Or you can just remember Phi function's formula, it's easy to remember indeed)

Answer 2

Well, I think a better approach will be to think it in terms of Euler's Totient function... Totient function gives you the number of numbers below a number n that are co prime with it i.e. GCD(n,x)=1 where

x < n .

Now the pairs till n is Pairs till n-1 + Pairs with n i.e (n- Totient function of n).

For Totient function refer Link

I think you will need to preprocess the totient of each number till 10^6 with the help of Totient Sieve just because a N* Root (N) will not pass in time.