前缀LCM构造——从后往前进行：ARC122E

本文主要是介绍前缀LCM构造——从后往前进行：ARC122E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://vjudge.net/contest/591700#problem/J

发现题目是一个类似前缀LCM的问题：

我们可以考虑从后往前构造，枚举最后一个数放什么

然后递归下去

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else#define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
//#define N
//#define M
//#define mo
int n, m, i, j, k, T;
vector<int>a; int lcm(int a, int b) {return a/__gcd(a, b)*b; 
}int dfs(vector<int>a) {if(a.size()==1) return printf("Yes\n%lld ", a[0]), 1; int n=a.size(), i, j; for(i=0; i<n; ++i) {k=1; debug("%d(%d %d) | %d\n", i, k, a[i], n); for(j=0; j<n; ++j) {if(i==j) continue; k=lcm(k, __gcd(a[i], a[j])); }if(k!=a[i]) {vector<int>b; for(j=0; j<n; ++j) if(i!=j) b.pb(a[j]); if(dfs(b)) { printf("%lld ", a[i]); return 1; }}}return 0; 
//	printf("No"); exit(0); 
}signed main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif
//	T=read();
//	while(T--) {
//
//	}n=read(); for(i=1; i<=n; ++i) k=read(), a.pb(k); if(!dfs(a)) printf("No\n"); return 0;
}

这篇关于前缀LCM构造——从后往前进行：ARC122E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---