Kuangbin数学训练营：EkkaDokka深度解析与应用

题目链接&＃xff1a;
传送门

#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N &＃61; 200010;ll t, w, k, n;int main() {scanf("%lld", &t);while(t--) {scanf("%lld", &w);ll m &＃61; 1;//当前数字中不包含偶数因子if(w & 1) printf("Case %d: Impossible\n", &＃43;&＃43;k);else {//不断地提取2的因子while(!(w & 1)) w /&＃61; 2, m *&＃61; 2;//输出答案printf("Case %lld: %lld %lld\n", &＃43;&＃43;k, w, m);}}
}


这道题要我们把数分解出两个因子&＃xff0c;一个为奇数&＃xff0c;一个为偶数。而且偶数因子还要尽可能的小。我们考虑一下这道题的情况&＃xff1a;
首先第一种就是没有偶数因子的情况&＃xff0c;这种情况下&＃xff0c;我们输出“Impossible”即可。
其余情况下&＃xff0c;我们可以想想如何才能得到一个最小的偶数因子&＃xff0c;首先由于另一个因子为奇数&＃xff0c;所以我们只要把含2的因子提取出来乘在一起就是最小的偶数因子了。这是因为如果此时把当前偶数因子的任何一个非1的因子提取出来给另一个因子时&＃xff0c;这个因子一定会变成偶因子&＃xff0c;不符合题意。
所以最终我们的做法就是不断的提取当前数的2的因子&＃xff0c;直到当前数是奇数为止&＃xff0c;然后输出答案即可。