Distribution in Metagonia(按条件拆分整数)

it2022-05-06  6

 Distribution in Metagonia(按条件拆分整数)

推荐阅读:https://blog.csdn.net/snowy_smile/article/details/49852091

 

最核心的一句话:if a family receives at least one cube, every prime divisor of the number of cubes received should be either 2 or 3, moreover if one family receives a > 0 cubes and another family in the same year receives b > 0 cubes then a should not be divisible by b and vice versa.

题意:把一个数分解为若干数,分解成的数的因子只能是2或者3。并且分解成的若干数两两不能整除。

思路:solve函数,首先两个while把因子2,3提取出来,存到now里,如果x==1就是全部都能提出来,答案就是没法分了,输出now。如果x还有剩余比如10 的 x = 5是没法分的,now = 2是已经提取出来的东西;现在的首要目标是把x=5给分开,它既不能有自身倍数有要是2或3的倍数,模拟题意得需要把x分成一个j(就是遍历3的倍数,找到比x小的哪一个,它一定符合条件),和一个p(p不知道符不符合条件,故需要再次判断,递归)。

 

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[2005]; ll cnt = 0; ll tot = 0; void solve( ll x, ll now ) { tot ++; while ( x%2==0 ) { x /= 2; now *= 2; } while ( x%3==0 ) { x /= 3; now *= 3; } if ( x==1 ) { a[cnt++] = now; } else { ll j; for ( j=3; j<x; j*=3 ) ; j /= 3; a[cnt++] = now*j; solve(x-j,now); } } int main() { freopen("distribution.in","r",stdin); freopen("distribution.out","w",stdout); ll listt,n,i,j,x; cin >> listt; while ( listt-- ) { tot = 0; cnt = 0; cin >> x; solve(x,1); cout << tot << endl; for ( i=0; i<cnt-1; i++ ) { cout << a[i] << " "; } cout << a[cnt-1] << endl; } return 0; }

 


最新回复(0)