题目链接
题目大意
问有没有生成的雪花节点数等于n?雪花是刚开始是一个点,后面从一个点连接K个节点,再从k个节点再连接K个点,easy版本是n<=1e6,hard version是n<=1e18
题解
easy版本暴力即可,直接预处理出所有的情况,刚开始雪花节点数目是,1 + k + k ^2,然后每次加K^i,hard version不能这样写,因为时间复杂度太高了,所以我们使用二分搜索,int是2^32,约为10位,long long 64位,约长18位,__int 128 128位。所以计算pow(k, i)不能直接算,会溢出,所以边乘边算。
代码
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
const ll P = 1e9, K = 2e18;
ll check(ll k, ll cnt)
{
__int128 s = 1, pr = 1;
for (ll i = 1; i <= cnt; i++) {
pr = pr * k;
s += pr;
if (s >= K)
return K;
}
ll res = s;
return res;
}
void solve()
{
ll n;
cin >> n;
for (ll i = 2; i <= 62; i++) {
ll l = 2, r = P;
while (l < r) {
ll mid = (l + r) / 2;
ll x = check(mid, i);
if (x == n) {
cout << "YES\n";
return;
} else if (x > n)
r = mid;
else
l = mid + 1;
}
}
cout << "NO\n";
}
int main()
{
IOS;
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}