E Math

题意

求数对 满足 ​

oeis题

设 ​​ 则有
$\frac{a^2+b^2}{1+ab}gcd(a,b)$

那么枚举 控制 不爆 ll 模拟即可

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int ll
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
typedef long long ll;
typedef vector<ll> vll;
vll pos;
void init() {
    int a = 0, b = 0, now = 0;
    pos.emplace_back(1);
    for (int i = 2; i * i * i <= 1e18; ++i) {
        a = i;
        b = i * i * i;
        pos.emplace_back(b);
        if (1e18 / b < i * i)
            continue;
        now = i * i * b - a;
        while (now <= 1e18) {
            pos.emplace_back(now);
            a = b;
            b = now;
            if (1e18 / b < i * i)
                break;
            now = i * i * b - a;
        }
    }
    sort(pos.begin(), pos.end());
}
void solve() {
    int n;
    cin >> n;
    int id = lower_bound(pos.begin(), pos.end(), n) - pos.begin();
    if (pos[id] == n)
        ++id;
    cout << id << endl;
}
signed main() {
    init();
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

J Counting Triangles

题意

一张无向完全图中，​​ 表示 顶点 ​​ 到顶点 ​​ 间有一条白边，否则为黑边。求图中三个顶点两两链接的边颜色相同的数量。

单纯的去找一个合法三元组满足上述关系时间复杂度为 ​​​ ，则考虑减去不合法情况。

一个三元组不合法即其中一条异色边，则有两个异色角。那么计算异色角即可求非法三角个数

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int ll
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define rrep(i, j, k) for (ll i = (ll)(j); i >= (ll)(k); i--)

typedef long long ll;
typedef vector<ll> vll;
namespace GenHelper {
unsigned z1, z2, z3, z4, b, u;
unsigned get() {
    b = ((z1 << 6) ^ z1) >> 13;
    z1 = ((z1 & 4294967294U) << 18) ^ b;
    b = ((z2 << 2) ^ z2) >> 27;
    z2 = ((z2 & 4294967288U) << 2) ^ b;
    b = ((z3 << 13) ^ z3) >> 21;
    z3 = ((z3 & 4294967280U) << 7) ^ b;
    b = ((z4 << 3) ^ z4) >> 12;
    z4 = ((z4 & 4294967168U) << 13) ^ b;
    return (z1 ^ z2 ^ z3 ^ z4);
}
bool read() {
    while (!u)
        u = get();
    bool res = u & 1;
    u >>= 1;
    return res;
}
void srand(int x) {
    z1 = x;
    z2 = (~x) ^ 0x233333333U;
    z3 = x ^ 0x1234598766U;
    z4 = (~x) + 51;
    u = 0;
}
} // namespace GenHelper
using namespace GenHelper;
int black[8005], white[8005];
signed main() {
    int n, seed;
    cin >> n >> seed;
    srand(seed);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (read())
                ++white[i], ++white[j];
            else
                ++black[i], ++black[j];
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += 1ll * white[i] * black[i];
    ans = 1ll * n * (n - 1) * (n - 2) / 6 - (ans / 2);
    cout << ans << endl;
}