题意：
给定数列a1,a2,....an
令ans=a1*a2*a2*....an
每次可以选择一个i（只能选一次），使得ai=ai*i
若操作后存在（2^n）| ans，输出最小的操作次数，否则输出-1
解：
可以发现，ans的结果与操作是可以分离开的
如果(2^n)|ans,则ans的2的幂次>=n
在输入的时候即可处理ans的2的幂次，记为cnt
cnt>=n,不需要处理，输出0
cnt<n,需要处理出 n-cnt个2
考虑下标i 的贡献，显然我们需要先操作贡献最大的
注意到只有偶数有贡献，预处理下标2的贡献
不需要对i分解，利用dp的思想（状态保存），f(i)=f(i/2)+1,递推即可
在给定n的范围内，把能贡献的数放进容器，维护降序，（sort(静态更优)，or priority_queue）
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=2e5+2e1;
array<ll,maxn>f;
ll div(ll x)
{
ll cnt=0;
while(x%2==0){cnt++;x/=2;}
return cnt;
}
void init()
{
f[2]=1;
for(int i=4;i<maxn;i+=2)
{
f[i]=f[i/2]+1ll;
}
}
void find_two(int n,ll cnt)
{
vector<ll>a;
for(int i=2;i<=n;i+=2)
{
a.emplace_back(f[i]);
}
sort(a.rbegin(),a.rend());
ll k=0,cur=0;
for(const auto&i:a)
{
cur+=i;k++;
if(cur>=cnt){cout<<k<<"\n";return;}
}
cout<<"-1\n";
}
void solve()
{
int n;cin>>n;
ll ans=0;ll x;
for(int i=0;i<n;i++)
{
cin>>x;
ans+=div(x);
}
ll cnt=n-ans;
if(cnt<=0)cout<<"0\n";
else
{
find_two(n,cnt);
}
}
int main()
{
init();
int t;cin>>t;
while(t--)
{
solve();
}
return 0;
}
标签：cnt,Divisibility,int,ll,贡献,a2,ans From： https://www.cnblogs.com/FeiShi/p/16798007.html