题目

题目大意：一棵树有n个结点，每个点的值分别是$i^2-1$，每条边的权值是$gcd(i^2-1,j^2-1)$ 求树边总权值的最小值 题目链接:https://www.luogu.com.cn/problem/P5560

思路

暴力打表可以发现 只有4 10需要特判 其他都是$n-1$

代码

#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<cctype> #include<ctime> #include<iostream> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<vector> #include<iomanip> #include<list> #include<bitset> #include<sstream> #include<fstream> #include<complex> #include<algorithm> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define int long long using namespace std; const int INF = 0x3f3f3f3f; signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; if(n==4) cout<<5<<endl; else if(n==10) cout<<11<<endl; else{ cout<<n-1<<endl; } } return 0; }