ICPC 2019 Preli: G – Pairs Forming GCD

0

Problem Link: https://algo.codemarshal.org/contests/icpc-dhaka-19-preli/problems/G

Solution Idea:

  • We have to find maximum G such that there exist at least P pairs of integers (X, Y), where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = G.
  • At first, let’s try to solve a subproblem where G=1. Can we calculate the number of pairs (X, Y) where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = 1?
  • As we know Euler totient or Phi function gives us a number of X which are coprime with Y. So Phi(Y) = number of X such that GCD(X,Y) = 1.
  • So Phi(1)+Phi(2)+Phi(3)+…….+Phi(N) = number of pair (X,Y) where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = 1.
  • Now if GCD(X,Y) = 1 then GCD(GX,GY) = G.
  • So we can pre-calculate Euler totient for 1 to N and then calculate the cumulative sum of this phi[] array and store it to phiSum[] array.
  • After this, we just have to binary search for the maximum answer on the new phiSum[] array.

#include <bits/stdc++.h>

using namespace std;

#define mx 10000007
int phi[mx];
long long phiSum[mx];

void euler_totient() {
    for(int i=0; i<mx; i++) phi[i]=i;
    for(int i=2; i<mx; i++) {
        if(phi[i]==i) {
            for(int j=i; j<mx; j+=i)
                phi[j]-=(phi[j]/i);
        }
    }
}

int solve(int n, long long p) {
    int lo=1,hi=n;
    int ret=-1;
    while(lo<=hi) {
        int mid=(lo+hi)/2;
        if(phiSum[mid]>=p) {
            ret=mid;
            hi=mid-1;
        } else {
            lo=mid+1;
        }
    }
    return ret;
}

int main() {

    euler_totient();
    for(int i=1; i<mx; i++) phiSum[i]+=phiSum[i-1]+phi[i]; //cumulative sum

    int t;
    scanf("%d",&t);
    for(int z=1; z<=t; z++) {
        long long n,p;
        scanf("%lld %lld",&n,&p);
        int ans=solve(n,p);
        printf("Case %d: ",z);
        if(ans!=-1)
            ans=n/ans;
        printf("%d\n",ans);
    }
    return 0;
}