CF1864C Divisor Chain 题解

Links

洛谷

Codeforce

Description

给定一个整数 \(x\)，目标是在最多 \(10^{3}\) 次操作内把 \(x\) 减到 \(1\)。

定义一个操作：选择一个 \(x\) 的因数 \(d\)，把 \(x\) 修改为 \(x-d\)。

同时还有一个额外的限制：相同的 \(d\) 值不能选择超过 \(2\) 次。

有 \(t\) 组测试数据。

数据范围：\(1\le t\le 10^3,2\le x\le 10^9\)。

Solution

一个很显然的事情是对于一个 \(x = 2^{k}\)，我们只需要 \(k\) 次操作就可以了，具体的，每次我们让 \(x\) 变为 \(\frac{x}{2}\)，直到 \(x = 1\)，这个过程每个数只会用一次。

因此让我们考虑如何让 \(x = 2^{k}\)，我们可以保留其二进制下最高位的 \(1\)，将其余的全部删除。具体的，我们每次将 \(x\) 消掉二进制下最低位的 \(1\)，这个过程可以用 \(\operatorname{lowbit}(x)\) 轻松完成。

Codes

#include <bits/stdc++.h>
using namespace std;
#define int long long
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int T,n;
int lowbit(int x)
{
    return (-x)&x;
}
vector<int> ans;
void solution()
{
    ans.clear();
    read(n);
    ans.push_back(n);
    int c = 0;
    while(n != lowbit(n))
    {
        ans.push_back(n - lowbit(n));
        n -= lowbit(n);
    }
    while(n > 1)
    {
        ans.push_back(n / 2);
        n /= 2;
    }
    writeln(ans.size());
    for(auto now:ans)
    {
        writesp(now);
    }
    puts("");
}
signed main()
{
    read(T);
    while(T--)
    {
        solution();
    }
    return 0;
}