ARC122E Increasing LCMs

ARC122E Increasing LCMs

考虑本质，要求每次添加的值要比前面的值多一点不同的质因子，即要求
$$\gcd ({\mathrm{lcm}}_{j=1}^{i-1}(a_j),a_i)<a_i$$
考虑从后往前填数，枚举寻找满足条件的数，添加进那一位即可。

若有多个数同时满足，随便选一个加进去即可，因为它满足比其他的多一点不同的质因子，定会使 $\mathrm{lcm}$ 增加。

发现求 $\mathrm{lcm}$ 的过程会爆炸，考虑优化。

原式中，对于每个质因子的指数，即先内部取 $\max$，再与 $a_i$ 对应指数的指数取 $\min$。

发现原式等价于
$${\mathrm{lcm}}_{j=1}^{i-1}(\gcd (a_j,a_i))$$
分类讨论

• 若质因子的指数中 $>=a_i$ 对应质数的指数时，应得 $a_i$ 对应质数的指数，二式满足。
• 若无质因子的指数中 $>=a_i$ 对应质数的指数时，应得指数最大值，二式也满足。

时间复杂度 $\mathcal{O}(n^3\log n)$。

#include

using namespace std;

#define int long long
typedef long long ll;
#define ha putchar(' ')
#define he putchar('\n')

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = x * 10 + c - '0', c = getchar();
	return x * f;
}

inline void write(int x)
{
	if(x < 0)
	{
		putchar('-');
		x = -x;
	}
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int _ = 110;

int n, a[_], ans[_];

bool flg[_];

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

signed main()
{
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int p = n; p >= 1; --p)
	{
		for(int i = 1; i <= n; ++i)
			if(!flg[i])
			{
				int lcm = 1, d;
				for(int j = 1; j <= n; ++j)
					if (j != i && !flg[j])
					{
						d = gcd(a[i], a[j]);
						lcm = lcm / gcd(lcm, d) * d;
					}
				if (lcm < a[i])
				{
					ans[p] = a[i];
					flg[i] = 1;
					break;
				}
			}
		if (!ans[p])
			return printf("No\n"), 0;
	}
	printf("Yes\n");
	for(int i = 1; i <= n; ++i) write(ans[i]), ha;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77