Weird GCD Value solution codechef

Weird GCD Value solution codechef


You are given two positive integers aa and bb, we define f(a,b)f(a,b) as the maximum value of |gcd(a,x)gcd(b,x)||gcd(a,x)−gcd(b,x)| where xx is some natural number. Formally,

f(a,b)=maxxN|gcd(a,x)gcd(b,x)|f(a,b)=maxx∈N|gcd(a,x)−gcd(b,x)| Weird GCD Value solution codechef

, where NN represents the set of natural numbers and gcd(a,b)gcd(a,b) represents the greatest common divisor of aa and bb.

You are given an integer kk. You need to find the number of ordered pairs (a,b)(a,b) (where a,ba,b are positive) such that f(a,b)=kf(a,b)=k.

Note that pairs (a,b)(a,b) and (b,a)(b,a) are considered different if aba≠b. For example, pair (1,2)(1,2) is not the same as (2,1)(2,1).

CodeChef Starters 18 Division 3 (Rated) - CodeChef

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each testcase contains a single integer kk.

Weird GCD Value solution codechef Output Format

For each testcase, output the number of ordered pairs (a,b)(a,b) such that f(a,b)=kf(a,b)=k.


  • 1T1061≤T≤106
  • 1k1061≤k≤106

Weird GCD Value solution codechef Sample Input 1 


Sample Output 1 


Explanation Weird GCD Value solution codechef

Test case 11: For k=1k=1, we see that f(1,2)=f(2,1)=1f(1,2)=f(2,1)=1. Therefore the answer is 22. It can be verified that there are no other pairs for which the ff value is 11.

Test case 22: For k=3k=3, there exists 66 ordered pairs for which the ff value is 33. One of them is (4,3)(4,3).

Leave a Comment