优秀的树
时间限制:C/C++ 2000MS,其他语言 4000MS
内存限制:C/C++ 256MB,其他语言 512MB描述
给定一棵树,其所有边权重均为 \(1\),定义 \(f(u)=Σ_v dis(u,v)\),v 表示树上的所有结点,\(dis(u,v)\) 表示结点 \(u\) 和 \(v\) 的简单路径的长度。
一棵树被称为“优秀”,当且仅当存在两个结点 \(u\) 和 \(v\) 满足 \(f(u)−f(v)=x\)。
给定 \(x\),求满足 “存在两个结点 \(u\) 和 \(v\) 满足 \(f(u)−f(v)=x\)” 成立的树最少有多少个结点。输入描述
输入有多组测试用例,第一行包含一个整数 \(t(1≤t≤10^5\)) ,表示接下来有 \(t\) 组测试用例。
每一个测试用例包含一个整数 \(x(1≤x≤10^{18}\))。输出描述
对每一个测试用例,输出一个整数,表示能满足条件被称为 “优秀” 的树结点最少为多少。
可以证明答案总是存在的。用例输入 1
3 2 3 114514
用例输出 1
4 5 678
提示
\(1≤t≤10^5\)
\(1≤x≤10^18\)
代码
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
long long x; scanf("%lld",&x);
long long k=sqrtl(x);
if(k*k==x) printf("%lld\n",(k<<1)+1);
else if(x<=k*(k+1) && !(x&1)) printf("%lld\n",(k<<1)+2);
else printf("%lld\n",(k<<1)+3);
}
return 0;
}
标签:10,结点,题解,优秀,long,测试用例,数学
From: https://www.cnblogs.com/jerrycyx/p/18339485