# MAXGCDVAL - Editorial

Setter:
Tester: Lavish Gupta and Abhinav Sharma
Editorialist: Taranpreet Singh

Easy-Medium

# PREREQUISITES

Euler’s totient function

# PROBLEM

Given two integers a and b, we define f(a, b) as the maximum value of |\gcd(a, x) - \gcd(b, x)| where x is some natural number. Formally,

f(a, b) = \max\limits_{x \in \mathbb{N}}| \gcd(a,x) - \gcd(b,x)|

(where \mathbb{N} represents the set of natural numbers and \gcd(a, b) represents the greatest common divisor of a and b)

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

# QUICK EXPLANATION

• A pair (a, b) shall have f(a, b) = (max(a, b)/g-1) * g where g = gcd(a, b)
• The number of pairs with f(a, b) = k shall have

# EXPLANATION

### Rewriting f(a, b)

Let’s consider a pair (a, b) with a \lt b and try to compute f(a, b). We want to find the maximum difference between gcd(a, x) and gcd(b, x). Sinec 1 \leq gcd(p, q) \leq p, q for any positive integers p and q, the maximum difference we can achieve is b-1, wheren gcd(b, x) = b and gcd(a, x) = 1

But this can happen only when gcd(a, b) = 1. Hence, for pairs (a, b) where a and b are co-prime, f(a, b) = max(a, b)-1.

Let’s generalize. Considering a pair (a, b) such that gcd(a, b) = g, then we can see that f(a/g, b/g) = max(a, b)/g-1 and f(a, b) = g * f(a/g, b/g) = g * (max(a, b)/g-1) = max(a, b) - g.

Hence, we can write f(a, b) = max(a, b) - gcd(a, b).

Additional observation is that f(a, a) = a-a = 0, So they do not affect our answer. Hence, we can consider only unordered pairs (a, b) where a \lt b and then multiply the answer by 2. So, For the rest of the editorial, assume a \lt b.

### The number of pairs with f(a, b) = K

We need number of pairs (a, b) where a \lt b such that b - gcd(a, b) = K. Assuming g = gcd(a, b), g must divide K as well.

Let’s substitute a = p*g and b = q*g. So we have q*g - g = K. We can see that p and q must be co-prime.

Hence, let’s iterate over all factors of K. If the current factor is g, we get q - 1 = K/g. So we must have q = 1+K/g. 1 \leq p \lt q and gcd(p, q) = 1. What is the number of values of p satisfying these conditions?

Let’s define function \phi(N) as the number of integers co-prime to N up to N. i.e. the number of integers x such that 1 \leq x \leq N and gcd(x, N) = 1.

Hence, for each factor g of K, we have \phi(K/g+1) choices of a and exactly one choice for b, contributing \phi(K/g+1) pairs to the number of pairs (a, b) with f(a, b) = K

### The \phi(N) function

The \phi(N) function is well known as the Euler totient function, which can be computed beforehand for all integers from 1 to M = 10^6+1 in O(M*log(log(M))) time in sieve style, as explained in this article.

It is important to compute \phi(N) for 10^6+1 as well, as when we consider K = 1000000 and g = 1,we need \phi(1000001).

Following pseudocode represent precomputing all answers from 1 to M assuming \phi(N) is already calculated.

for g in 1 to M:
for k = g to M, step size g:
ans[k] += phi[k/g+1]


# TIME COMPLEXITY

The time complexity of the above solution is O(M*log(M) + T), though the time limit was relaxed enough to allow certain T * \sqrt M kind of approaches to pass.

# SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const int N = 1e6+5;

int phi[N], ans[N];

void precompute_phi()
{
phi[0] = 0;
phi[1] = 1;
for(int i = 2; i < N; i++)
phi[i] = i;

for(int i = 2; i < N; i++)
{
if(phi[i] == i)
{
for(int j = i; j < N; j += i)
phi[j] -= phi[j] / i;
}
}
}

{
for(int i = 1; i < N; i++)
{
for(int j = i; j < N; j += i)
{
// i is a factor of j
ans[j] += 2 * phi[i + 1];
}
}
}

int32_t main()
{
IOS;
precompute_phi();
int T; cin >> T;
while(T--)
{
int k; cin >> k;
cout << ans[k] << endl;
}
return 0;
}

Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
assert('a'<=g and g<='z');
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 1000000;
const int MAX_N = 1000000 ;
#define ll long long

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_len = 0;
int max_n = 0;
int max_k = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
int max_s = 0 ;

int n;
vector<int> factors[MAX_N+1] ;
vector<int> euler(MAX_N + 10) ;

void pre()
{
for(int i = 1 ; i <= MAX_N+1 ; i++)
euler[i] = i ;
for(int i = 1 ; i <= MAX_N ; i++)
{
for(int j = i ; j <= MAX_N ; j += i)
{
factors[j].push_back(i) ;
}
if(factors[i].size() == 2)
{
for(int j = i ; j <= MAX_N+1 ; j += i)
{
euler[j] = (euler[j]/i)*(i-1) ;
}
}
}
return ;
}

void solve()
{
n = readIntLn(1 , MAX_N) ;
ll ans = 0 ;
for(int i = 0 ; i < factors[n].size() ; i++)
{
ll g = factors[n][i] ;
}
ans *= 2 ;
cout << ans << '\n' ;
return ;
}

signed main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.txt", "r" , stdin);
freopen("outputf.txt", "w" , stdout);
#endif
// fast;

int t = 1;

pre() ;

for(int i=1;i<=t;i++)
{
solve();
}

assert(getchar() == -1);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"maxN : " << max_n << '\n';
// cerr<<"maxK : " << max_k << '\n';
// cerr<<"Sum of lengths : " << sum_len << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}

Tester's Solution 2
#include <bits/stdc++.h>
using namespace std;

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 1e6;
const int MAX_N = 1e6+5;
const int MAX_SUM_LEN = 1e5;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

int n;
vector<long long> ans(MAX_N);
vector<int> phi(MAX_N);

void pre(){
phi[0]=0;
phi[1]=1;

for(int i = 2; i <= MAX_N; i++)
phi[i] = i;

for(int i = 2; i <= MAX_N; i++){
if(phi[i] == i){
for (int j = i; j <= MAX_N; j += i)
phi[j] -= phi[j] / i;
}
}

for(int i=1; i<MAX_N ; i++){
for(int j = i; j<MAX_N; j+=i){
ans[j] += phi[i+1];
}
}
}

void solve()
{

sum_len += n;

int res = 0;
for(int i=1; i*i<=n; i++){
if(n%i==0){
res += phi[i+1];
if(i*i!=n) res+=phi[n/i+1];
}
}

cout<<2*res<<'\n';

}

signed main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;

pre();

int t = 1;

for(int i=1;i<=t;i++)
{
solve();
}

assert(getchar() == -1);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_len << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}

Editorialist's Solution
import java.util.*;
import java.io.*;
class MAXGCDVAL{
//SOLUTION BEGIN
int MX = (int)1000000;
int[] ans;
void pre() throws Exception{
int[] spf = spf(1+MX), phi = phi(spf, 1+MX); ans = new int[1+MX];
for(int p = 1; p <= MX; p++)
for(int q = p; q <= MX; q+= p)
ans[q] += phi[q/p+1];
}
void solve(int TC) throws Exception{
pn(2*ans[ni()]);
}
//euler phi function
int[] phi(int[] spf, int max){
int[] phi = new int[1+max];
phi[1] = 1;
for(int i = 2; i <= max; i++){
int r = i/spf[i];
if(spf[r] == spf[i])phi[i] = phi[r]*spf[i];
else phi[i] = phi[r]*(spf[i]-1);
}
return phi;
}
int[] spf(int max){
int[] spf = new int[1+max];
for(int i = 2; i<= max; i++)
if(spf[i] == 0)
for(int j = i; j <= max; j += i)
if(spf[j] == 0)
spf[j] = i;
return spf;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MAXGCDVAL().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

3 Likes

How is f(a,b)=g*f(a/g,b/g) ? in rewriting f(a,b) section @taran_1407

1 Like

Can someone help me figure out why my solution TLEd? Solution: 54221733 | CodeChef
The complexity is ok, the code runs in ~0.5s on my machine and ~0.6s on CodeChef IDE.

Switching to a faster input method makes it AC (Solution: 54223811 | CodeChef), but that doesn’t make a lot of sense because

1. It’s unreasonable that reading 1e6 lines would take more than 5s.
2. I have a submission on the INTEST problem where the same input method reads 1e7 lines in ~1s.

How is f(a,b)=g*f(a/g,b/g) ? in rewriting f(a,b) section ?

1 Like

wondering the same

Let’s assume a = p*g, b = q*g, gcd(p, q) = 1, p< q.

So we have f(p, q) = q-1 which we get by choosing x = q, giving |gcd(q, q)-gcd(p, q)| = q-1. We want to find f(a, b).

For f(a, b), choosing x = b, which gives f(a, b) = b - g.

Consider gcd(a, b, x). It would be same as gcd(g, x). So we can write |gcd(a, x)-gcd(b,x)| = gcd(g, x)*|gcd(a,x)/gcd(g, x) - gcd(b,x)/gcd(g, x)| = gcd(g, x)*f(a/gcd(g, x), b/gcd(g,x)).

It is best for choose x such that g is a factor of x.

2 Likes