目录
题目概述
原题参考：C. Divisor Chain
给出一个数x，可以对他做以下的变换
- 若y是x的除数，x-=y
- 任意的y不能使用超过两次
可以证明的是，对于任意的数，都可以在1000次操作内将其变成1，请输出将x变为1的操作次数与过程
思路想法
首先是如果随机除以因子的话，那么肯定会很麻烦，因为求因子麻烦，记录因子的使用次数也麻烦，那么就想如何快速的给出因子，而且最好是不一样的，正常的十进制不好做，思考二进制的转化，由此可以得到触发，二进制的最后一位1以后的数是这个数的因子，因此我们可以将任意一个数转化为2的次方，转化为2的次方之后，出现一个问题，如何将其转化为1？毫无疑问，这是不好做的，但是我们很容易将一个2的次方转化为2，再用2转化为1，然后再来思考是否满足题目的第二个要求，明显，对于任意一个因子，只可能最多使用两次（降为2次方一次，降为1一次）；至于1000次操作以内，那更是绰绰有余，题目的范围是1e9，“右移”最多32次，“左移”最多32次
参考代码
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
ll x;
ll lowbit(ll x) {return x&-x;}
void solve() {
ll cnt = 0;
vector<ll> ans;
cin >> x;
ans.push_back(x);
while(x-lowbit(x)) {
x -= lowbit(x);
ans.push_back(x);
}
while(x != 2) {
x >>= 1;
ans.push_back(x);
}
ans.push_back(1);
cout << ans.size() << endl;
for(auto x:ans) cout << x << " ";
cout << endl;
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
做题反思
记录一下，这是第一个10分钟以内昨晚的c题hhh，今天的爽局，对于数字转化的题目，如果十进制想不到好办法，可以转化为二进制思考，二进制的因子很好用