題目鏈接：https://ac.nowcoder.com/acm/contest/100672#question
C.是毛毛蟲嗎？
思路：
其實很簡單，假設我們要滿足題目所給條件，那么這個毛毛蟲最壞情況下肯定是一條如下圖所示的無向圖
右端省略號為對稱圖形 ，其中紅線為毛毛蟲的主體
那我們可以知道，只要對于其中任意一個節點增加一個，那么就無法構成毛毛蟲
再總結一下，即只要一個節點有三個子節點，且這三個子節點都含有一個子節點（不為父節點）
那么就無法構成毛毛蟲
代碼：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;void solve()
{int n;cin >> n;vector<vector<int> >a(n + 1);for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;a[x].push_back(y);a[y].push_back(x);}for (int i = 1; i <= n; i++){if (a[i].size() >= 3){int sum = 0;for (int j = 0; j < a[i].size(); j++){int t = a[i][j];if (a[t].size() > 1)sum++;}if (sum >= 3) {cout << "NO" << endl;return;}}}cout << "YES" << endl;
}int main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}K.友善的數
思路：
首先，只有x或y有一個為1，那么必定無法找出
那么接下來我們考慮什么情況這個數k與x,y不互質
可以顯然看出，我們最小的情況肯定是 Px*Py ，其中P為構成x/y的最小質因數
那么就分兩種情況
①.gcd(x,y) == 1
此時x和y互質，那么此時只能選x和y的最小質因數
②.gcd(x,y) != 1
此時x和y有著公約數，那么我們可以考慮旋轉公約數的最小質因子，但是不能保證其一定比x和y的最小質因數之積小，所以還需要取min
對于如何選取x和y的質因數，我們可以想到歐拉篩，在歐拉篩中我們保證每次篩選都是最小質因數的i倍，所以我們便可以定義一個數組用于儲存每個數的最小質因數，同時預處理一下
代碼：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;ll gcd(ll a,ll b)
{return !b ? a : gcd(b, a % b);
}
const int N = 2e5+1;
bool isp[N + 1];
vector<int> p;
int minp[N + 1];void els()
{memset(isp, true, sizeof isp);isp[0] = isp[1] = false;for (int i = 2; i <= N; i++){if (isp[i]) p.push_back(i), minp[i] = i;for (int j = 0; j < p.size() && p[j] * i <=N; j++){minp[p[j] * i] = p[j];isp[p[j] * i] = false;if (i % p[j] == 0) break;}}
}void solve()
{ll x, y;cin >> x >> y;if (x == 1 || y == 1){cout << -1 << endl;return;}if (gcd(x,y) == 1){cout << (ll)(minp[x]) * (ll)(minp[y]) << endl;}else{cout << min((ll)minp[gcd(x,y)], (ll)minp[x] * (ll)minp[y]) << endl;}
}int main()
{els();cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}
