How to solve this GCD problem?

Here is the link of the problem: Problem

Basically the Problem statement is;

find out how many pair (x,y) can be possible in range N, which gcd is greater than 1. Here pair (x,y) and (y,x) consider as same pair. 1<=x,y<=N.

Constraints:

N (1≤N≤10^5)

Looking at the constraints it is obvious that Brutforce approach would not work here, I 'm trying to solve this problem using Euler’s Totient Function but I don’t know how can I use ETF in this problem. Any help would be appriciated.

https://www.geeksforgeeks.org/queries-to-count-the-number-of-unordered-co-prime-pairs-from-1-to-n/

Once go through this method and code, answer to your code will be( ((N*(N-1))/2)+N) -answer from above code. i.e., total no of pairs from 1 to n - no of pairs with gcd=1;

1 Like

calculate etf values for all 1-10^5 (let etf[i] denote that)
for each i in 1-10^5 calculate c[i]=i-etf[i]
convert array into prefix sum array
answer queries in O(1)

1 Like

Can you please explain it better or share some links to related topic??

so far I have written this python code it does well but still it’s still approx O(N√N) time complexity

def phi(n):
# ETF in O (sq_root (n)) T.C.
result = n # Initialize result as n
p = 2
while p * p <= n:

    # Check if p is a prime factor.
    if (n % p == 0):

        # If yes, then update n and result
        while n % p == 0:
            n = n // p
        result = result * (1.0 - (1.0 / float(p)))
    p = p + 1

if n > 1:
    result = result * (1.0 - (1.0 / float(n)))

return int(result)

def pwg(n):
res = sum(range(1, n + 1))
for i in range(1, n + 1):
res -= phi(i)
return res

you have to calculate all etf values first using a sieve-
check this
then solve queries in O(1)
sample ac code

@echo_abhinav I did what you said but still I’m getting time limit exceded error can you please tell me where I’m doing wrong?

Here is the python code

tc = int(input())
for case in range(1, tc + 1):
n = int(input())
# calculating ETF using seive
phi = [0] * (n + 1)

for i in range(n + 1):
    phi[i] = i
for p in range(2, n + 1):
    if phi[p] == p:
        phi[p] = p - 1  # if p is not changed then it is prime
        
        # update all the multiples of that p
        for i in range(2 * p, n + 1, p):                
            phi[i] = (phi[i] // p) * (p - 1)

# prefix arr of phi
for i in range(1, n + 1):
    phi[i] = i - phi[i]  # values that gave gcd > 1
    phi[i] += phi[i - 1]  # cumulative sums of values

print(f"Case {case}: {phi[n]}")

you are calculating phi[] for every test case you should be doing it only once.

2 Likes

@ echo_abhinav Do you mean I should do this ?

n = 100001
phi = [0] * (n + 1)

for i in range(n + 1):
     phi[i] = i
for p in range(2, n + 1):
    if phi[p] == p:
        phi[p] = p - 1  # if p is not changed then it is prime

        # update all the multiples of that p
        for i in range(2 * p, n + 1, p):
            phi[i] = (phi[i] // p) * (p - 1)

# prefix arr of phi
for i in range(1, n + 1):
    phi[i] = i - phi[i]  # values that gave gcd > 1
    phi[i] += phi[i - 1]  # cumulative sums of values
#Done calculating all the values upto 1000001

test_case = int(input())
for case in range(1, tc + 1):
    k = int(input())
    # calculating ETF using seive
    print(f"Case {case}: {phi[k]}")

I tried doing this but it’s still giving Time Limit Exceded Error on Spoj :expressionless:

Time limit is 0.5 sec try doing this in C++ and also use fast Input and Output

I accidently mentioned you in a post then edited it again…