D 签到

题意

梗题：给你一个 $n$ $(n\le10^{15})$, 如果 $1^2 + 2^2 + … + n^2$ 是完全平方数，输出 “Fake news!”, 否则输出 “Nobody knows it better than me!”

思路

刚开始写了个暴力，算出 1, 24 是唯一合法的解。但是由于太暴力了，怕 wa，所以写了个二分判断完全平方数

代码

#include <bits/stdc++.h>

using namespace std;
using int128_t = __int128;

int128_t sqrt(int128_t x) {
    int128_t l = 1, r = x;
    while (r - l > 2) {
        int128_t m = l + (r - l) / 2;
        if (m * m <= x) l = m;
        else r = m - 1;
    }
    return l;
}

bool judge(int128_t n) {
    int128_t sum = n * (n + 1) * (2 * n + 1) / 6;
    int128_t temp = sqrt(sum);
    return temp * temp == sum;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long n;
        scanf("%lld", &n);
        puts(judge(n) ? "Fake news!" : "Nobody knows it better than me!");
    }
    return 0;
}