EOJ 2020.7 E 因数串 题解

题目大意

因数串，指的是由正整数 $a$ 所有因数所构成的一个数列，需要满足从数列的第 $2$ 个数开始，每个数都必须由其前一个数乘以某个质数或除以某个质数得出的。

因数串需要保证正整数 $a$ 所有因数都会出现且只出现一次。现在 Cuber QQ 会告诉你正整数 $a$ ，你需要给出任意一个因数串。

其中正整数 $a=\prod _ {i=1} ^ n p_i ^ {k_i} $ 。

解题思路

这个题目是真的难想，看到这个题目就其实有点懵。

首先，可以让这个串是由1开始的。

那么先以第一组为例，从$p^1$到$p^k$。

然后可以得到他们分别乘以$p_1^1$到$p_1^{k_1}$次方。

以此类推，就可以得到最终的因数串。

具体的原因，可以看官方题解。

需要将所有的约数按照一定的排列，使得相邻的两个数只相差一个质因子。

倘若我们用广义 $X$ 进制编码的形式（大概可以这么命名吧？）来表示每一个因数，即将每一个因数都按照质因数分解的形式，每一位上的数分别表示包含某一个质数的个数。例如可能包含的质数有 $2,3,5,7$ ，则 $600=2^3\cdot 3\cdot 5^2$ 可以用 $(3120)_X$ 来表示。

用这样编码的好处是，我们要求“相邻的两个数只相差一个质因子”，也就是在两个数的编码中有且仅有其中的某一位相差 $1$ 。

这样构造的思路，我们可以从格雷码中学到一些经验，用类似格雷码的方式构造就可以得到一个合法的解了。

真的。。这是人能想到的吗。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll p[20], k[20];
vector<ll> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i] >> k[i];
	}
	ll c = 1;
	v.push_back(c);
	for (int i = 1; i <= k[1]; i++)	c *= p[1], v.push_back(c);
	for (int i = 2; i <= n; i++) {
		int len1 = v.size();
		for (int j = 1; j <= k[i]; j++) {
			int len2 = v.size();
			for (int l = 0; l < len1; l++)	v.push_back(v[len2 - l - 1] * p[i]);
		}
	}
	for (auto x : v)	cout << x << endl;
}