题解-CF1744D

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

把我卡了好久……

题面大意

给定整数序列 $S$ ，你可以选出一个操作集 $Q$，满足 $\forall q \in Q,q \in [1,n]$，然后将所有 $S_q$ 替换成 $qS_q$，求要使原序列能被 $2^n$ 整除所需的最少操作次数。

解题思路

只记录每个数 $2$ 的因子的出现次数即可。

同时，为了确保操作次数最少，我们肯定首选 $2$ 的次幂最多的数字进行乘法。

所以我们可以设计一个简单的 dp，定义 $f_i$ 为 $i$ 含有 $2$ 的因子的个数，我们不难得到 $f_i = \begin{cases}f_\frac{i}{2}+1 & (i = 2k,k \in N) \\ 0\end{cases}$。

最后将 $f$ 数组排序，从大往小减即可。

#include <stdio.h>
#include <algorithm>
#include <string.h>

typedef long long i64;
const i64 mod = 1, maxn = 200007;

i64 T, n, li[maxn], lg[maxn], res, p2, t2, solved, logg[maxn], op, rem;

int main()
{
    scanf("%lld", &T);

    while (T--)
    {
        scanf("%lld", &n);
        rem = n;
        op = 0;

        memset(logg, 0, sizeof logg);
        logg[2] = 1;
        for (int i = 3; i <= n; i++)
            if (!(i & 1))
                logg[i] = logg[i >> 1] + 1;
            else
                logg[i] = 0;

        for (int i = 0; i < n; i++)
            scanf("%lld", li + i);

        for (int i = 0; i < n; i++)
            while (!(li[i] & 1))
                li[i] >>= 1,
                    rem--;

        if (rem <= 0)
            printf("0\n");
        else
        {
            std::sort(logg, logg + n + 1);
            for (int i = n; i; i--)
            {
                rem -= logg[i];
                op++;
                if (rem <= 0)
                {
                    printf("%d\n", op);
                    break;
                }
            }

            if (rem > 0)
                printf("-1\n");
        }
    }
    return 0;
}