PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Hazem Tarek
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Bitmasking
PROBLEM:
You are given a set A=[A_1,A_2,\dots ,A_N], where A_i \le C for each valid i. Find any set B=[B_1,B_2,\dots,B_M] such that:
- A is divisible by B.
- 2 \le B_i \le C, for each valid i.
- M is the smallest positive integer such that there is at least one set satisfying the previous two conditions.
The set A is said to be divisible by B if each integer in A is divisible by at least one (not necessarily the same for each of them) integer in B.
EXPLANATION:
Observation: An optimal set of B exists which contains only prime numbers.
- Suppose we have a number X in set B which divides [A_1,A_3,\dots,A_y] in set A. Then any prime divisor of X, say P_x will always divide [A_1,A_3,\dots,A_y]. It may be also possible to divide some other number of set A by P_x which was not divisible by X. Hence it is always optimal to have a set B which contains only prime numbers,
Subtask 1:
Here, C \le 50.
Since the value of C is small enough, we can iterate over all masks of primes that are less than C and check if the current mask covers the set A. Finally, we will output the minimal such set.
Solution
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 50
int main()
{
vector <int> primes;
for(int i=2; i<=MAX_N; i++){
bool ok = true;
for(int j=2; j<i; j++)
ok &= (i%j != 0);
if(ok)
primes.push_back(i);
}
int t;
scanf("%d",&t);
while(t--){
int n ,c;
scanf("%d%d",&n,&c);
vector <int> pr;
for(int i=0; i<primes.size() && primes[i]<=c; i++)
pr.push_back(primes[i]);
vector <int> a;
for(int x,i=0; i<n; i++){
scanf("%d",&x);
int mask = 0;
for(int j=0; j<pr.size(); j++)
mask |= (x%pr[j] == 0)<<j;
a.push_back(mask);
}
int ans = INT_MAX;
for(int mask = 1; mask < 1<<pr.size(); mask++){
bool ok = true;
for(int&i : a)
ok &= (i&mask) != 0;
if(ok && __builtin_popcount(mask) < __builtin_popcount(ans))
ans = mask;
}
printf("%d\n",__builtin_popcount(ans));
for(int i=0; i<pr.size(); i++) if(ans>>i&1)
printf("%d ",pr[i]);
printf("\n");
}
}
Subtask 2:
it is guaranteed that M \le 2.
If the gcd of all the numbers in set A is not equal to 1, then in this we can have our set B to contain only one element and that element is gcd of all the numbers in set A. Since gcd will be dividing all the elements of the set A.
If gcd equals 1, then we will iterate over all possible B_0 and let g be the gcd of the elements of set A that are not divisible by B_0. Then there must exist at least one g \neq 1 and therefore our set B will be [B_0, g]
Solution
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 7500
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n ,c ,g = 0;
scanf("%d%d",&n,&c);
vector <int> a(n);
for(int&i : a){
scanf("%d",&i);
g = g? __gcd(g ,i) : i;
}
if(g != 1){
printf("1\n%d\n",g);
continue;
}
for(int i=2; i<=c; i++){
g = 0;
for(int&j : a) if(j%i != 0)
g = g? __gcd(g ,j) : j;
if(g != 1){
printf("2\n%d %d\n",i,g);
break;
}
}
}
}
Subtask 3:
The condition of M \le 2 is removed.
Claim: There can be at most 1 prime factor of X greater than \sqrt{X}.
Proof:
If possible let there be two distinct prime factors of X which are greater than \sqrt{X}, say P_1 and P_2. As both P_1 and P_2 are different prime factors of X their product P_x=P_1*P_2 should also be the factor of X. But P_x would exceed X as both P_1 and P_2 are greater than \sqrt{X}, which contradicts our assumption, hence there can only be one prime factor of X greater than \sqrt{X}.
Let’s modify the solution of Subtask1 1, a little. A better approach is to iterate over all of primes subsets that are less than or equal to \sqrt{C}. Now for every element in set A that isn’t covered by this mask, we add its prime divisor to the set.
The answer is the set with minimal size overall masks.
Solutions
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 7500
int main()
{
vector <int> primes ,lp(MAX_N+1);
for(int i=2; i<=MAX_N; i++) if(!lp[i]){
for(int j=i; j<=MAX_N; j+=i)
lp[j] = lp[j]? lp[j] : i;
primes.push_back(i);
}
int t;
scanf("%d",&t);
while(t--){
int n ,c;
scanf("%d%d",&n,&c);
vector <int> pr{2};
for(int i=1; i<primes.size() && primes[i]*primes[i] <= c; i++)
pr.push_back(primes[i]);
vector <pair<int ,int>> a;
for(int x,i=0; i<n; i++){
scanf("%d",&x);
int mask = 0;
for( ; x > 1 && lp[x] <= pr.back(); x /= lp[x])
mask |= 1<<(find(pr.begin() ,pr.end() ,lp[x])-pr.begin());
a.push_back({mask ,x});
}
bitset <MAX_N+1> ans ,cur;
ans.set();
for(int mask = 0; mask < 1<<pr.size(); mask++){
cur.reset();
for(int i=0; i<pr.size(); i++) if(mask>>i&1)
cur.set(pr[i]);
for(auto&p : a) if((p.first&mask) == 0)
cur.set(p.second);
if(!cur[1] && cur.count() < ans.count())
swap(ans ,cur);
}
printf("%d\n",ans.count());
for(int i=0; i<=MAX_N; i++) if(ans[i])
printf("%d ",i);
printf("\n");
}
}
Subtask 4:
The idea is that instead of brute-forcing the mask of small primes and then checking what numbers are already divisible by something. We can precalculate what will we have to additionally pay for each mask.
Hence, In general, our solution will be:
- Factorize each number into a mask of small primes with one big prime (possibly).
- Group the numbers by their big prime.
- For each big prime find out for which masks, We’ll have to take this big prime additionally,
and add 1 to answer for those masks (numbers without big prime add inf to bad masks)
Suppose we are working with big prime P, then numbers with this big prime could only have small primes up to C/P. So, We can mark bad masks only on those small primes and all the other primes are not significant for this big prime.
So for any big prime P, let’s say that there are k small primes that are smaller than C/P
in O(2^k * k) we can mark all the bad masks for this prime. And then we can make a query to do 1 on all bad masks of size k and any mask of size P-k. We will then collect them with SOS- DP
We can also group big primes with the same k in batches and do the O(2^k * k) propagation at once.
TIME COMPLEXITY:
O(2^k*k)
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
#define MAX_C 7500
#define MAX_P 23
vector <int> primes ,lp(MAX_C+1 ,-1);
vector <int> bad[MAX_C+1] ,b[MAX_P+1];
int a[(1<<MAX_P)+1] ,c[(1<<MAX_P)+1];
void solve(){
int n ,C;
scanf("%d%d",&n,&C);
int m = 1 ,k = 1;
while(primes[m]*primes[m+1] <= C) m++;
while(k < primes.size() && primes[k] <= C) k++;
for(int i = 0; i < k; i++)
bad[i].clear();
for(int mask = 0; mask < 1<<m; mask++)
a[mask] = 0;
for(int i = 0; i <= m; i++)
b[i] = vector<int>(1<<i);
for(int i = 0; i < n; i++){
int x ,mask = (1<<m) - 1;
scanf("%d",&x);
for( ; x > 1 && lp[x] < m; x /= primes[lp[x]])
mask &= ~(1<<lp[x]);
if(x == 1)
a[mask] = MAX_C;
else
bad[lp[x]].push_back(mask);
}
for(int l = m; l < k; l += m){
int sz = 0;
while(sz < m && primes[l]*primes[sz] <= C) sz++;
for(int mask = 0; mask < 1<<sz; mask++)
c[mask] = 0;
for(int i = l; i < min(k ,l + m); i++)
for(int&x : bad[i])
c[((1<<sz)-1) & x] |= 1<<(i-l);
for(int mask = (1<<sz)-1; mask; mask--)
for(int i = 0; i < sz; i++) if(mask>>i&1)
c[mask^(1<<i)] |= c[mask];
for(int mask = 0; mask < 1<<sz; mask++)
b[sz][mask] += __builtin_popcount(c[mask]);
}
for(int i = 0; i < m; i++){
for(int mask = 0; mask < 1<<i; mask++)
a[mask + (1<<m) - (1<<i)] += b[i][mask];
for(int mask = 0; mask < 1<<m; mask++) if((mask>>i&1) == 0)
a[mask] += a[mask^(1<<i)];
}
for(int mask = 0; mask < 1<<m; mask++)
a[mask] += b[m][mask];
pair <int ,int> ans = {MAX_C ,0};
for(int mask = 0; mask < 1<<m; mask++)
ans = min(ans ,make_pair(a[mask] + __builtin_popcount(mask) ,mask));
printf("%d\n",ans.first);
for(int i = 0; i < m; i++) if(ans.second>>i&1)
printf("%d ",primes[i]);
for(int i = m; i < k; i++){
for(int&x : bad[i]) if((x&ans.second) == ans.second){
printf("%d ",primes[i]);
break;
}
}
printf("\n");
}
int main()
{
for(int i = 2; i <= MAX_C; i++) if(lp[i] == -1){
for(int j = i; j <= MAX_C; j += i)
lp[j] = lp[j] != -1? lp[j] : primes.size();
primes.push_back(i);
}
int t;
scanf("%d",&t);
while(t--)
solve();
}
Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
//#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
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;
}
assert(l<=x&&x<=r);
return x;
} else {
cout<<g<<" abc "<<((int)(g))<<endl;
cerr<<g<<" abc "<<((int)(g))<<endl;
fflush(stdout);
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,' ');
}
bool primus[7605];
int a[7505];
int sum_c=0;
int great=3000,greatcount=0;
vi ffew;
vi pp[7505];
int cntr[7605];
int here[7505];
int fans[1<<23];
vi tens[25];
void solve() {
int n=readIntSp(1,7499),c=readIntLn(n+1,7500);
// int n=7499,c=7500;
// int n,c;
// cin>>n>>c;
memset(here,0,sizeof(here));
fr(i,1,c)
pp[i].clear();
fr(i,1,n) {
// cin>>a[i];
if(i!=n)
a[i]=readIntSp(2,c);
else
a[i]=readIntLn(2,c);
here[a[i]]=1;
}
fr(i,2,c)
if(here[i])
for(int j=2*i; j<=c; j+=i)
here[j]=0;
vi red;
fr(i,2,c)
if(here[i])
red.pb(i);
n=sz(red);
int ms=0;
while(ffew[ms]*ffew[ms+1]<=c)
ms++;
memset(fans,0,(1<<ms)*sizeof(int));
int lp=0;
while(ffew[lp]<=c)
lp++;
rep(i,0,lp)
pp[ffew[i]].clear();
sum_c+=c;
assert(sum_c<=100000);
if(c>great)
greatcount++;
assert(greatcount<=1);
for(int i:red) {
int mask=0;
for(int j=0; j<ms; j++)
if(i%ffew[j]==0) {
mask|=(1<<j);
while(i%ffew[j]==0)
i/=ffew[j];
}
int te=sqrt(i)-1;
while(te*te<i)
te++;
if(te*te==i)
i=te;
pp[i].pb(mask);
}
int troll=1;
for(int i=ms; i<lp; i+=62) {
int ppu=0;
while(ffew[ppu]*ffew[i]<=c)
ppu++;
tens[troll].assign((1<<ppu),0);
for(int l=0; l<62&&i+l<lp; l++)
for(int k:pp[ffew[i+l]])
tens[troll][((1<<ppu)-1)^k]|=(1LL<<l);
for(int l=0; l<ppu; l++)
for(int j=0; j<(1<<ppu); j++)
if((j>>l)&1)
tens[troll][j^(1<<l)]|=tens[troll][j];
for(int i=0; i<(1<<ms); i++)
fans[i]+=__builtin_popcountll(tens[troll][i&((1<<ppu)-1)]);
troll++;
}
int ppu=ms;
tens[0].assign((1<<ppu),0);
for(int i:pp[1])
tens[0][i^((1<<ppu)-1)]+=100;
for(int l=0; l<ppu; l++)
for(int j=(1<<ppu)-1; j>=0; j--)
if((j>>l)&1)
tens[0][j^(1<<l)]+=tens[0][j];
for(int i=0; i<(1<<ppu); i++)
fans[i]+=tens[0][i];
for(int i=0; i<(1<<ppu); i++)
fans[i]+=__builtin_popcount(i);
int bestans=infi,mask=0;
for(int i=0; i<(1<<ms); i++)
if(fans[i]<=bestans) {
bestans=fans[i];
mask=i;
}
troll=1;
vi ans;
for(int i=ms; i<lp; i+=62,troll++)
for(int j=0; j<62; j++)
if((tens[troll][mask&(sz(tens[troll])-1)]>>j)&1) {
ans.pb(ffew[i+j]);
}
for(int j=0; j<ms; j++)
if((mask>>j)&1)
ans.pb(ffew[j]);
cout<<sz(ans)<<endl;
for(int i:ans)
cout<<i<<" ";
cout<<endl;
}
void pre() {
memset(primus,1,sizeof(primus));
primus[0]=primus[1]=0;
fr(i,2,7600)
if(primus[i]) {
cntr[i]=sz(ffew);
ffew.pb(i);
for(int j=i*i; j<=7600; j+=i)
primus[j]=0;
}
}
signed main() {
pre();
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
int t=readIntLn(1,1000);
// int t=1;
// cin>>t;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}