CHRIST - Editorial

PROBLEM LINK:

Practice

DIFFICULTY:

Easy

PREREQUISITES:

Maths, Number theory

PROBLEM:

We have to find N numbers such that GCD of all possible pairs of N numbers must be N, and minimize the sum of N numbers.

EXPLANATION:

This problem can be solved by finding a set of N numbers such that the GCD of all possible pairs equals to 1 and then multiply the set of N numbers by N, so we can find N numbers such that their GCD equals to N

We can have many set of N numbers such that the GCD of all possible pairs equals to 1, but here we also have to satisfy the above condition ( i.e. minimize sum of N numbers). So, for this, we need to use 1 and first N-1 prime numbers . Therefore, we get a set of N numbers such that the GCD of all possible pairs equals to 1.

Finally, multiply the set of N numbers by N to get the required N numbers.

SOLUTIONS:

Setter’s Solution
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long int ll;

typedef vector<ll> vi;

vector<bool> prime;

void sieve()

{

  prime.resize(10000001,1);

  prime[0]=0;

  for(ll i=2;i<=10000000;i++)

  if(prime[i])

  for(ll j=i*i;j<=10000000;j+=i)

  prime[j]=0;

}

int main()

{

fast;

ll n,cnt=0;

cin>>n;

sieve();

  for(int i=1;cnt<n;i++)

  {

    if(prime[i])

    {

    cout<<n*i<<" ";

    cnt++;

    }

  }

cout<<endl;

}