GCDPERM - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: raysh_07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Knowledge of GCD

PROBLEM:

You’re given N and K. From the integers \{1, 2, \ldots, N\}, find a subset of size K such that its GCD is maximum among all GCDs of size-K subsets.

EXPLANATION:

Suppose we want get a GCD of exactly g by picking K integers. How can we achieve this?
Well, since g must be the greatest common divisor of the numbers, certainly every number we choose should be a multiple of g.
That means our options are to choose from g, 2g, 3g, \ldots

It should be easy to see that, as long as we choose g as one of the K numbers, the GCD of everything will be exactly g (everything is a multiple of g so the GCD is \geq g, and g itself being chosen means the GCD can’t exceed g, so it must equal g).

We need to pick K distinct numbers, so the best we can do is pick g, 2g, 3g, \ldots, K\cdot g.
That is,

  • If K\cdot g \leq N, it’s possible to get a GCD of g by picking g, 2g, 3g, \ldots, K\cdot g
  • If K\cdot g\gt N, it’s impossible to get a GCD of g, since it’s impossible to pick K distinct numbers that are multiples of g.

So, all we need to do is find the largest g such that K\cdot g \leq N.
This can be done with a loop, or directly by noting that g = \left\lfloor \frac{N}{K} \right\rfloor.

Once you’ve found g, simply print g, 2g, 3g, \ldots, K\cdot g as the answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    print(*list(range(n//k, n+1, n//k))[:k])
2

Another method to solve this particular question :
C++ Code :

include <bits/stdc++.h>
using namespace std;

int main() {
int t; cin>>t;
while(t–){
long long n,k; cin>>n>>k;
long long x = n/k;
long long ans = x;
while(k–){
cout<<ans<<" ";
ans += x;
}
cout<<endl;
}
return 0;

}