MAXGCDVAL - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

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

DIFFICULTY

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;
        }
    }
}

void precompute_answer()
{
    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();
    precompute_answer();
    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 readString(int l,int r,char endd){
    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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,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] ;
        ll ad = (n+g)/g ;
        ans += euler[ad] ;
    }   
    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;
        
    t = readIntLn(1,MAX_T);
    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 readString(int l,int r,char endd){
    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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,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()
{

    
   n = readIntLn(1, 1e6);

   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;
    
    t = readIntLn(1,MAX_T);
    
    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;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        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());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

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

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

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

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