PROBLEM LINK:
Setter: Pranav Reddy
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
EASY
PREREQUISITES:
Prime factorization
PROBLEM:
There is rectangular screen in coordinate plane from (0, 0) to (N, M). We need to divide the rectangle into vertical columns with equal size with borders as integer coordinates. Then each column is further divided into windows with the following properties:
-
For a column, the size of each window must be same and must have borders as integer coordinates.
-
There must be atleast two windows in a single column.
-
No two windows in different columns have the same y coordinate for horizontal edges, except for the borders of the screen.
We need to output the maximum number of columns that can be created.
EXPLANATION:
-
Let there be a total of tot columns in the final answer with the number of windows in each column as c_1, c_2 \dots c_{tot}.
-
To ensure the horizontal edges of two windows of different columns i and j have different y coordinates, we need to have gcd(c_i, c_j) =1.
-
We can easily prove this by contradiction: Let gcd(c_i, c_j) =k \gt 1. Then, c_i = k \cdot p and c_j = k\cdot q for some positive integers p and q. Now, window in column i has size s_i = \frac{M}{k \cdot p} and window in column j has size s_j = \frac{M}{k \cdot q}. It can be observed clearly that p^{th} window from the bottom in column i has a horizontal edge which will have the same y coordinate the q^{th} window from the bottom in column j. In other words, p \cdot s_i = q \cdot s_j = \frac{M}{k} \lt M. We arrived at a contradiction because our assumption is wrong. Therefore, gcd(c_i, c_j) must be equal to 1.
-
Now our main goal is to maximize the value of tot. This can be realised by first doing the prime factorization of M. This can be done in O(\sqrt M) by the classic prime factorization method. Let there be a total of y primes and let M = p_1^{x_1} \cdot p_2^{x_2} \dots p_y^{x_y}.
-
The maximum value of tot we can have is y with possible c_1 = p_1, c_2=p_2 \dots c_y = p_y. Why? Suppose tot \gt y. Then atleast two columns i and j will have gcd(c_i, c_j) \neq 1. This is because of pigeon-hole principle. If tot \gt y and we only have y primes available and every column i must have c_i \gt 1, atleast one prime must be repeated in two columns which results in their gcd greater than 1. Therefore, tot = y is the maximum possible.
-
We are now left to find the maximum number less than tot which is divisible by N for the borders of columns to have integer coordinates. This can be simply done by iterating over i from 1 to tot and choosing maximum i for which N is divisible by i.
TIME COMPLEXITY:
O(\sqrt M) for each test case.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n, m;
cin >> n >> m;
int primes = 0;
for (int i = 2; i * i <= m; i++)
{
if (m % i == 0)
{
primes++;
while (m % i == 0)
{
m /= i;
}
}
}
if (m > 1)
primes++;
int ans = 0;
for (int i = 1; i <= primes; i++)
{
if (n % i == 0)
{
ans = i;
}
}
cout << ans << endl;
}
return 0;
}
Setter's solution
// Official Statement at https://www.notion.so/ChefWM-679a2962e13c4597b8bb69f934fc70f8
#include <cstdlib>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace std::chrono;
#define int long long
#define ld long double
#define sz(c) ((int)c.size())
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int inf = 1e18;
const int mod = 1e9 + 7;
const int mod2 = 998244353;
int distinctPrimeFactors(int n) {
int answer=0;
vector<int> primeFactors;
while (n % 2 == 0) {
primeFactors.push_back(2);
n = n/2;
}
for(int i=3;i*i<=n;i+=2) {
while(n%i==0) {
primeFactors.push_back(i);
n = n/i;
}
}
if (n>2) primeFactors.push_back(n);
set<int> distinctFactors;
for(int x : primeFactors) distinctFactors.insert(x);
return distinctFactors.size();
}
signed main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
auto startTime = high_resolution_clock::now();
int tt;
cin>>tt;
while(tt--) {
int n,m;
cin>>n>>m;
int distinctFactors = distinctPrimeFactors(m);
if(distinctFactors==0) {
cout<<0<<endl;
continue;
}
vector<int> divisorsOfN;
for(int i=1;i*i<=n;i++) {
if(i*i==n) divisorsOfN.push_back(i);
else if(n%i==0) {
divisorsOfN.push_back(i);
divisorsOfN.push_back(n/i);
}
}
sort(divisorsOfN.begin(), divisorsOfN.end());
int ans=0;
for(int i=1;i<(int)divisorsOfN.size();i++) {
ans = divisorsOfN[i-1];
if(divisorsOfN[i]>distinctFactors) break;
}
if(divisorsOfN[divisorsOfN.size()-1] <= distinctFactors) ans = divisorsOfN[divisorsOfN.size()-1];
cout<<ans<<endl;
}
auto stopTime = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stopTime - startTime);
//cout<<"Program ran for "<<(ld)duration.count()/1e6<<" "<<"seconds"<<endl;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
------------------------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 = 500;
const int MAX_N = 1000000000;
const int MAX_Q = 100000;
const int MAX_val = 1000000000;
const int MAX_SUM_N = 200000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll p = 1000000007;
ll sum_nk = 0 ;
int get_cnt_prime(int n)
{
int cnt = 0 ;
for(int i = 2 ; i*i <= n ; i++)
{
if(n%i == 0)
{
cnt++ ;
while(n%i == 0)
n /= i ;
}
}
if(n != 1)
cnt++ ;
return cnt ;
}
void solve()
{
int n = readIntSp(1 , MAX_N) ;
int m = readIntLn(1 , MAX_N) ;
int num = get_cnt_prime(m) ;
if(num == 0)
cout << 0 << '\n' ;
else
{
for(int i = num ; i > 0 ; i--)
{
if(n%i == 0)
{
cerr << "min_divisible = " << i << endl ;
cout << i << '\n' ;
return ;
}
}
}
return ;
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
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_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr << "Sum o f product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Please comment below if you have any questions, alternate solutions, or suggestions. 
