Codeforces Round 883 (Div. 3) - E2. Rudolf and Snowflakes (hard version)

Solost

2023 年 07 月 08 日

153 次浏览

暂无评论

235字数

题目题解

## 题目链接

[链接](https://codeforces.com/contest/1846/problem/E2)

## 题目大意

问有没有生成的雪花节点数等于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)不能直接算，会溢出，所以边乘边算。

## 代码

```cpp
#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;
}
```

最后修改：2023 年 07 月 08 日