题意
给你 $n$ 个元素，$m$ 个方程。
每个方程形如 $$ \begin{align} \gcd(x_i, y_i)=c_i\ \mathrm{lcm}(x_i,y_i) = d_i \end{align} $$ 之类的形式。
询问这个方程组是否有解。有 $T$ 组数据。
$1 \le T \le 10, 1 \le n, m \le 200$ 。
题解
这道题是一个很巧妙的 $2-SAT$ 。不会的话，可以参考 2-SAT 问题与解法小结 。
我们可以这样设计变量，令变量 $a[i][j][k]$ 表示是否有 $\displaystyle p^j | x_i$ ，上面限制就能表示出来啦。
一开始觉得每个质因子可以单独考虑，后来发现要一起考虑，因为别的 $gcd, lcm$ 会限制这个的次数。
具体来说是这样的。
-
$\gcd(x_i, y_i) = c_i$
那么我们首先考虑 $x_i, y_i$ 中与 $c_i$ 互质的质因子 $p$ 。
对于这些质因子 $p$ ， $x, y$ 不能同时出现我们连一条 $a[x][p][1] \to \neg a[y][p][1]$ 的边（注意要连逆否命题的边）。
那么我们接下来可以考虑，假设 $c_i$ 存在质因子 $p$ 的最高次数为 $k$ 。
那么 $x_i, y_i$ 两个数对于 $p$ 的最低次数为 $k$ ，且必有一个数次数刚好为 $k$ ，那么连三条边就行了。
首先强制使得 $a[x][p][k], a[y][p][k]$ 为真。（也就是连一条从真到假的边就行了）
然后如果 $a[x][p][k + 1]$ 为真，那么要使得 $a[y][p][k + 1]$ 为假。（逆否也要）
这是因为不能存在两个次数都 $\ge k+1$ 。
-
$\mathrm{lcm} (x_i, y_i) = d_i$
同样先考虑 $x_i, y_i$ 中与 $d_i$ 互质的质因子 $p$ 。
对于这些质因子 $p$ ， $x, y$ 不能包含，所以强制使得 $a[x][p][1], a[y][p][1]$ 为假。
那么我们接下来可以考虑，假设 $d_i$ 存在质因子 $p$ 的最高次数为 $k$ 。
同上， $x_i, y_i$ 两个数对于 $p$ 的最高次数为 $k$ ，且必有一个数次数刚好为 $k$ ，那么连三条边就行了。
强制使得 $a[x][p][k+1], a[y][p][k+1]$ 为假。
然后如果 $a[x][p][k]$ 为假，那么要使得 $a[y][p][k]$ 为真。（逆否也要）
连完这些，还要记得 $a[x][p][k]$ 为真时，$a[x][p][k - 1]$ 也要为真。
然后就可以轻松愉悦的码码码了。
然后对于 $a[x][p][k]$ 标号的时候，可以用 std :: map<int, map<int, map<int, int> > > id 来实现qwq
STL大法好！！！
复杂度是 $O(Tm \log 10^9)$ 的。
总结
对于 $\gcd, \mathrm{lcm}$ 的题，可以对于指数进行考虑，就变成了高维的取 $\min$ 和取 $\max$ 问题。
代码
建议 抄 学习一下我的代码
1#include <bits/stdc++.h> 2 3#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i) 4#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i) 5#define Set(a, v) memset(a, v, sizeof(a)) 6#define Cpy(a, b) memcpy(a, b, sizeof(a)) 7#define debug(x) cout << #x << ": " << x << endl 8#define DEBUG(...) fprintf(stderr, __VA_ARGS__) 9#define fir first 10#define sec second 11 12using namespace std; 13 14typedef pair<int, int> PII; 15 16inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;} 17inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;} 18 19inline int read() { 20 int x = 0, fh = 1; char ch = getchar(); 21 for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1; 22 for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); 23 return x * fh; 24} 25 26void File() { 27#ifdef zjp_shadow 28 freopen ("1318.in", "r", stdin); 29 freopen ("1318.out", "w", stdout); 30#endif 31} 32 33const int N = 2e4 + 1e3; 34struct Two_Sat { 35 36 int n; vector<int> G[N]; 37 void Init(int n) { 38 this -> n = n; 39 For (i, 2, n << 1 | 1) G[i].clear(); 40 } 41 42 void Add(int x, int xv, int y, int yv) { 43 x = x << 1 | xv; y = y << 1 | yv; 44 G[x].push_back(y); G[y ^ 1].push_back(x ^ 1); 45 } 46 47 int sccno[N], scc_cnt, dfn[N], lowlink[N], sta[N], top, clk; 48 void Tarjan(int u, int fa = 0) { 49 dfn[u] = lowlink[u] = ++ clk; sta[++ top] = u; 50 for (int v : G[u]) 51 if (!dfn[v]) Tarjan(v, u), chkmin(lowlink[u], lowlink[v]); 52 else if (!sccno[v]) chkmin(lowlink[u], dfn[v]); 53 if (dfn[u] == lowlink[u]) { 54 ++ scc_cnt; int now; 55 do sccno[now = sta[top --]] = scc_cnt; while (u != now); 56 } 57 } 58 59 bool Solve(int n) { 60 this -> n = n; 61 For (i, 2, n << 1 | 1) dfn[i] = sccno[i] = 0; scc_cnt = clk = 0; 62 For (i, 2, n << 1 | 1) if (!dfn[i]) Tarjan(i); 63 For (i, 1, n) if (sccno[i << 1] == sccno[i << 1 | 1]) return false; 64 return true; 65 } 66 67} T; 68 69int n, m; 70 71struct Equation { 72 int x, y, val, opt; 73} lt[N]; 74 75set<int> fac[N]; 76void Get_Factor(int x, int val) { 77 For (i, 2, sqrt(val + .5)) if (!(val % i)) { 78 while (!(val % i)) val /= i; fac[x].insert(i); 79 } 80 if (val > 1) fac[x].insert(val); 81} 82 83int Size; map<int, map<int, map<int, int> > > id; 84int Get_Id(int x, int p, int k) { 85 if (!id[p][x][k]) id[p][x][k] = ++ Size; return id[p][x][k]; 86} 87 88void Build_Again() { 89 for (auto i : id) for (auto j : i.sec) { 90 int Last = 0; for (auto k : j.sec) { 91 if (Last) T.Add(k.sec, 1, Last, 1); Last = k.sec; 92 } 93 } 94 id.clear(); 95} 96 97void Modify(int x, int val) { 98 T.Add(x, val ^ 1, x, val); 99} 100 101void Resolve(int x, int y, int opt, int val) { 102 103 set<int> fx = fac[x]; set<int> fy = fac[y]; 104 int tmp = val; 105 For (i, 2, sqrt(val + .5)) if (!(val % i)) { 106 while (!(val % i)) val /= i; fx.erase(i); fy.erase(i); 107 } 108 if (val > 1) fx.erase(val), fy.erase(val); val = tmp; 109 110 if (opt == 1) { 111 for (auto prime : fx) Modify(Get_Id(x, prime, 1), 0); 112 for (auto prime : fy) Modify(Get_Id(y, prime, 1), 0); 113 } else { 114 vector<int> V; 115 set_union(fx.begin(), fx.end(), fy.begin(), fy.end(), inserter(V, V.begin())); 116 for (int prime : V) { 117 T.Add(Get_Id(x, prime, 1), 1, Get_Id(y, prime, 1), 0); 118 T.Add(Get_Id(y, prime, 1), 1, Get_Id(x, prime, 1), 0); 119 } 120 } 121 122 register int i = 2; 123 while (val > 1) { 124 if (!(val % i)) { 125 int cnt = 1; while (!(val % i)) val /= i, ++ cnt; 126 if (!opt) { 127 Modify(Get_Id(x, i, cnt), 1); 128 Modify(Get_Id(y, i, cnt), 1); 129 T.Add(Get_Id(x, i, cnt + 1), 1, Get_Id(y, i, cnt + 1), 0); 130 } else { 131 Modify(Get_Id(x, i, cnt + 1), 0); 132 Modify(Get_Id(y, i, cnt + 1), 0); 133 T.Add(Get_Id(x, i, cnt), 0, Get_Id(y, i, cnt), 1); 134 } 135 } 136 ++ i; if (i * i > val) i = val; 137 } 138} 139 140int main () { 141 142 File(); 143 144 for (int cases = read(); cases; -- cases) { 145 146 Size = 0; 147 148 n = read(); m = read(); 149 For (i, 1, n) fac[i].clear(); 150 For (i, 1, m) { 151 static char str[5]; 152 scanf ("%s", str + 1); 153 int opt = str[1] == 'L', x = read(), y = read(), val = read(); 154 lt[i] = (Equation) {x, y, val, opt}; 155 Get_Factor(x, val); Get_Factor(y, val); 156 } 157 158 For (i, 1, m) Resolve(lt[i].x, lt[i].y, lt[i].opt, lt[i].val); Build_Again(); 159 160 puts(T.Solve(Size) ? "Solution exists" : "Solution does not exist"); T.Init(Size); 161 162 } 163 164 return 0; 165}