Question link
Atcoder direction
Luogu direction
Question solution
Fairy question!
considering
a
i
<
2
m
a_i<2m
The strange restriction of ai?<2m can be obtained for
k
?
2
i
(
k
k*2^i(k
k?2i(k is an odd number
)
)
), you can only select
1
1
1, and one must be chosen because
1
?
2
m
1-2m
The only odd numbers 1?2m are
m
m
m
Consider what form satisfies the condition, i.e. for
k
1
?
2
i
,
k
2
?
2
j
k_1*2^i,k_2*2^j
k12i,k22j, do not exist
i
<
j
i
i
i
i calculates the conditions
k
k
The range of k
L
k
,
R
k
L_k,R_k
Lk?,Rk? (there is indeed a range of occurrences of numbers)
How to solve it specifically
L
k
,
R
k
L_k,R_k
Lk?,Rk here with
L
k
L_k
Lk? For example, just enumerate from large to small
k
k
k, then
L
k
=
max
?
{
L
d
+
1
}
(
k
∣
d
)
L_k=\max\{L_d + 1\}(k|d)
Lk?=max{Ld? + 1}(k∣d)
then put
a
i
a_i
ai? Seized into
k
?
2
i
k*2^i
The form of k?2i is easy to know when
L
[
i
]
≤
k
≤
R
[
i
]
L[i]\le k\le R[i]
There is a solution when L[i]≤k≤R[i], otherwise there is no solution (there are also some unsolvable conditions where all odd numbers cannot be obtained
k
k
k or
L
k
>
R
k
L_k>R_k
Lk?>Rk?)
time complexity
O
(
n
ln
?
n
)
O(n\ln n)
O(nlnn)
#include <bits/stdc + + .h>
using namespace std;
const int N=1000100;
int n,m,a[N],L[N],R[N];
bool vis[N];
inline int read(){<!-- -->
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1) + (FF<<3) + ch-48;
return FF*RR;
}
int find(int x){<!-- -->
for(int i=0,bs=1;;i + + ,bs<<=1) if(bs>x) return i-1;
}
int ed(){<!-- -->
for(int i=1;i<=n;i + + ) puts("No");
exit(0);
}
int main(){<!-- -->
n=read(),m=read();
for(int i=1;i<=n;i + + ) a[i]=read(),vis[a[i]]=1;
for(int i=1;i<=m<<1;i + =2){<!-- -->
bool flg=0;
for(int j=i;j<=m<<1;j<<=1) if(vis[j]){<!-- --> flg=1;break;}
if(!flg) ed();
}
for(int i=1;i<=m<<1;i + =2) R[i]=find((m<<1)/i);
for(int i=1;i<=m<<1;i + =2){<!-- -->
while(R[i]>=0 & amp; & amp;!vis[i<<R[i]]) R[i]--;
for(int j=3*i;j<=m<<1;j + =i<<1) R[j]=min(R[j],R[i]-1);
}
for(int i=(m<<1)-1;i>=1;i-=2){<!-- -->
for(int j=3*i;j<=m<<1;j + =i<<1) L[i]=max(L[i],L[j] + 1);
while((i<<L[i])<=(m<<1) & amp; & amp;!vis[i<<L[i]]) L[i] + + ;
}
for(int i=1;i<=m<<1;i + =2) if(L[i]>R[i]) ed();
for(int i=1;i<=n;i + + ){<!-- -->
int k=0;
while(~a[i] & amp;1) a[i]>>=1,k + + ;
if(L[a[i]]<=k & amp; & amp;k<=R[a[i]]) puts("Yes");
else puts("No");
}
fprintf(stderr,"%d ms\\
",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}