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 除以多少。

     while(n %  == ) {

         n /= ;

         mul *= ;

     }

     while(n %  == ) {

         n /= ;

         mul *= ;

     }

     if(n == ) {

         num[m++] = mul;

         return ;

     }

第二步：那么更重要的问题是如果 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。

 else {

         long long x = ;

         while(x *  < n) {

             x *= ;

         }

         n -= x;

         num[m++] = x * mul;

         solve(n, mul);

     }

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <queue>

 #include <map>

 #include <cstdlib>

 using namespace std;

 typedef long long LL;

 LL num[];

 int m;

 /*

 题意：将n拆成m个数，这m个数的表示是

 */

 void solve(LL n, LL mul)

 {

     while(n %  == ) {

         n /= ;

         mul *= ;

     }

     while(n %  == ) {

         n /= ;

         mul *= ;

     }

     if(n == ) {

         num[m++] = mul;

         return ;

     } else {

         long long x = ;

         while(x *  < n) {

             x *= ;

         }

         n -= x;

         num[m++] = x * mul;

         solve(n, mul);

     }

 }

 int main()

 {

     freopen("distribution.in", "r", stdin);

     freopen("distribution.out", "w", stdout);

     int t;

     cin >> t;

     while(t--) {

         LL n;

         cin >> n;

         m = ;

         solve(n, );

         cout << m << endl;

         for(int i = ; i < m; i++) {

             cout << num[i];

             if(i != m-) cout << " ";

             else cout << endl;

         }

     }

     return ;

 }

巴特西

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

最新文章

热门文章