275C. k-Multiple Free Set

Problem Link


In this problem,a subset consists of some numbers which number is not divisible by k and in the set there will be no number which is multiple of k

First sort all the numbers. Also consider an empty set of integers S, which represents the output. For each integer x in the sequence, If it’s not divisible by k, just pick it and insert it into S. Otherwise if it’s divisible by k check if x / k is in S or not. If it’s not in S insert x into S otherwise skip x.

View Code

 #include <bits/stdc++.h>
using namespace std;
#define INF 10000000

typedef long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(si ::iterator it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end()) // for set,map
#define present(c,x) (find(all(c),x) != (c).end()) // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)
si st;

int main()
int n,k;
int a[n];
{int x;


else {
int x=a[i]/k;





Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s