2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest D：Distribution in Metagonia（构造）

http://codeforces.com/gym/100801/attachments

题意：给出一个数n（1 <= n <= 1e18），将 n 拆成 m 个整数，其中 m 必须是 2^x * 3^y 的形式，并且 x 和 y 不能被彼此整除，输出 m 并将这些整数输出。

思路：Inspired by http://blog.csdn.net/snowy_smile/article/details/49852091 。

第一步：因为要求的 m 是 2^x * 3^y 的形式，所以如果 n 可以直接被 2^x * 3^y 整除的话，即 n % （2^x * 3^y） == 0，那么就可以直接输出 n 了。如果不能被直接整除的话，我们可以先将 n 拆解成不能被 3 和 2 整除的形式，这里的话用一个 mul 记录 n 除以多少。

 1     while(n % 3 == 0) {
 2         n /= 3;
 3         mul *= 3;
 4     }
 5     while(n % 2 == 0) {
 6         n /= 2;
 7         mul *= 2;
 8     }
 9     if(n == 1) {
10         num[m++] = mul;
11         return ;
12     }

第二步：那么更重要的问题是如果 n 不能被 2 或 3 整除，同时也不为 1 时应该怎么做。因为不能被 2 整除，所以这时的 n 必定是一个奇数。那么我们可以将 n 减去 w，w = 3^y && w < n，我们所做的是将 n 拆解出一个 w（w必定为奇数），那么剩下的 n 就是一个偶数了，这个时候我们又能回到第一步进行递归求解了。因为我们拆出的 w 也是组成 n 的一部分，因此要记录下来，记录的数值是 w * mul，因为我们前面 n 除以了一些 2 和 3 ，我们用 mul 记录下来了，因此这个时候要乘回去，所以是 w * mul。

1 else {
2         long long x = 3;
3         while(x * 3 < n) {
4             x *= 3;
5         }
6         n -= x;
7         num[m++] = x * mul;
8         solve(n, mul);
9     }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <queue>
 7 #include <map>
 8 #include <cstdlib>
 9 using namespace std;
10 typedef long long LL;
11 LL num[150];
12 int m;
13 /*
14 题意：将n拆成m个数，这m个数的表示是
15 */
16 void solve(LL n, LL mul)
17 {
18     while(n % 3 == 0) {
19         n /= 3;
20         mul *= 3;
21     }
22     while(n % 2 == 0) {
23         n /= 2;
24         mul *= 2;
25     }
26     if(n == 1) {
27         num[m++] = mul;
28         return ;
29     } else {
30         long long x = 3;
31         while(x * 3 < n) {
32             x *= 3;
33         }
34         n -= x;
35         num[m++] = x * mul;
36         solve(n, mul);
37     }
38 }
39 
40 int main()
41 {
42     freopen("distribution.in", "r", stdin);
43     freopen("distribution.out", "w", stdout);
44     int t;
45     cin >> t;
46     while(t--) {
47         LL n;
48         cin >> n;
49         m = 0;
50         solve(n, 1);
51         cout << m << endl;
52         for(int i = 0; i < m; i++) {
53             cout << num[i];
54             if(i != m-1) cout << " ";
55             else cout << endl;
56         }
57     }
58     return 0;
59 }

2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest D：Distribution in Metagonia（构造）

相关推荐