Given an integer N, find the sum of GCD(i, N) where i = 1 to N. GCD denotes the greatest common divisor. Provide the answer modulus 10^{9} + 7.
Example 1:
Input: N = 2
Output: 3
Explanation:
GCD(1,2)+GCD(2,2) = 1 + 2 = 3
Ã¢â¬â¹Example 2:
Input: N = 10
Output: 27
Explanation:
GCD(1,10)+GCD(2,10)+...
+GCD(9, 10)+GCD(10, 10)=1+2+..+1+10=27
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sumOfGCDofPairs() which takes N as inputs and returns the answer.
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def sumOfGCDofPairs (self, N):
        #complete the function here

Solutions:
def getCount(d, n):
	no = n // d
	result = no
	for p in range(2, int(pow(no, 1 / 2)) + 1):
		if no % p == 0:
			while no % p == 0:
				no //= p
			result -= result // p
	if no > 1:
		result -= result // no
	return result

class Solution:

	def sumOfGCDofPairs(self, N):
		res = 0
		n = N
		for i in range(1, int(pow(n, 1 / 2)) + 1):
			if n % i == 0:
				d1 = i
				d2 = n // i
				res += d1 * getCount(d1, n)
				if d1 != d2:
					res += d2 * getCount(d2, n)
		return res


class Solution:

	def sumOfGCDofPairs(self, n):
		divisors = []
		(d, j) = (1, -1)
		while d * d < n:
			if n % d == 0:
				j += 1
				divisors.append([d, n // d, 0])
			d += 1
		if d * d == n:
			divisors.append([d, d, 0])
		while j >= 0:
			divisors.append([divisors[j][1], divisors[j][0], 0])
			j -= 1
		numDivisors = len(divisors)
		sum = 0
		j = numDivisors - 1
		while j >= 0:
			m = divisors[j][1]
			for i in range(j + 1, numDivisors):
				if divisors[i][0] % divisors[j][0] == 0:
					m -= divisors[i][2]
			divisors[j][2] = m
			sum += divisors[j][0] * m
			j -= 1
		return sum


import math

class Solution:

	def count(self, d, n):
		x = n // d
		res = x
		for i in range(2, int(math.sqrt(n)) + 1):
			if x % i == 0:
				while x % i == 0:
					x = x // i
				res -= res // i
		if x > 1:
			res -= res // x
		return res

	def sumOfGCDofPairs(self, N):
		res = 0
		for i in range(1, int(math.sqrt(N)) + 1):
			if N % i == 0:
				d = N // i
				res += i * self.count(i, N) % (10 ** 9 + 7)
				res %= 10 ** 9 + 7
				if d != i:
					res += d * self.count(d, N) % (10 ** 9 + 7)
					res %= 10 ** 9 + 7
		return res


import math

class Solution:

	def sumOfGCDofPairs(self, n):

		def count(d, n):
			x = n // d
			res = x
			s = int(math.sqrt(n))
			for i in range(2, s + 1):
				if x % i == 0:
					while x % i == 0:
						x = x // i
					res -= res // i
			if x > 1:
				res -= res // x
			return res
		res = 0
		s = int(math.sqrt(n))
		for i in range(1, s + 1):
			if n % i == 0:
				d = n // i
				res += i * count(i, n) % 1000000007
				res %= 1000000007
				if d != i:
					res += d * count(d, n) % 1000000007
					res %= 1000000007
		return res