1

# ICPC 2019 Preli: G – Pairs Forming GCD

0

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