19牛客第四场D(数学+思维)
题目
给出一个数n,要求输出尽可能少的一组数,使得这一组数或 的结果恰好等于n,而且给出的数都是3的倍数,题目保证一定有解.
思路
这个题咋看之下不太好做,因为3的倍数在二进制上并没有明显规律.
显然我们发现如果$n$本身就是3的倍数的话,那么直接输出n即可.
问题就在于如果$n$不是3的倍数的情况.
关于这种构造题,我们还是考虑结果是$n$经过某种变换得到的.
有个首要的前提是$2^imod3$ 的结果不会是0.要么是1,要么是2.(想不明白的时候可以用唯一分解定理思考一下)
也就是对于一个n来说,如果将其拆成二进制,也就是$2^i$的和的形式,那么所有的二进制为1的位会有两种可能,要么取余3为1,要么取余3位2.
如果n只有两个位是1,那么除非n本身就是3的倍数,否则无论如何也不会凑出来的.(因为是或嘛)
我们发现,如果n%3等于1,那么我们考虑怎么去掉这个1.
-
n的二进制幂中存在一个余数为1的(称p),一个余数为2的(称q).那么答案可以是{n-p,p+q}
- n的二进制幂中不存在余数为1的,三个余数为2的(称p,q,r),那么答案就是{n-p-q,p+q+r}
- n的二进制幂中存在三个余数为1的(称p,q,r),不存在余数为2的,那么答案就是{n-p,p+q+r}
如果n%3等于2,那么只需要将上面的判断反过来即可.
还是不太好想的.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 3000000+100
ll n;
const int Inf = 0x3f3f3f3f;
template<typename T>
inline void read(T &X) {
X = 0;
char ch = 0;
T op = 1;
for (; ch > '9' || ch < '0'; ch = getchar())
if (ch == '-') op = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
X = (X << 3) + (X << 1) + ch - 48;
X *= op;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld", &n);
if (n % 3 == 0) {
printf("1 %lld\n", n);
} else {
ll k = n;
vector<ll> num[2];
int cnt = 0;
while (k > 0) {
if (k & 1) {
num[cnt & 1].push_back(1LL << cnt);
}
k >>= 1;
++cnt;
}
int len1 = num[0].size(), len2 = num[1].size();
if (n % 3 == 1) {
if (len1 >= 2) {
printf("2 %lld %lld\n", n - num[0][0], n - num[0][1]);
} else if (len1 == 1) {
printf("2 %lld %lld\n", n - num[0][0], num[0][0] + num[1][0]);
} else {
printf("2 %lld %lld\n", n - num[1][0] - num[1][1], num[1][0] + num[1][1] + num[1][2]);
}
} else {
if (len2 >= 2) {
printf("2 %lld %lld\n", n - num[1][0], n - num[1][1]);
} else if (len2 == 1) {
printf("2 %lld %lld\n", n - num[1][0], num[1][0] + num[0][0]);
} else {
printf("2 %lld %lld\n", n - num[0][0] - num[0][1], num[0][0] + num[0][1] + num[0][2]);
}
}
}
}
return 0;
}
