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