提瓦特之王：（此处省略若干个字）

pypy3 解法, 执行用时: 1466ms, 内存消耗: 40040K, 提交时间: 2022-06-02 00:48:37

import os,sys
from random import randint
from io import BytesIO, IOBase

from collections import defaultdict,deque,Counter
from bisect import bisect_left,bisect_right
from heapq import heappush,heappop
from functools import lru_cache
from itertools import accumulate
import math

# Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# for _ in range(int(input())):
#     n = int(input())
#     a = list(map(int, input().split(' ')))

# n, x, c = list(map(int, input().split(' ')))
# a = list(map(int, input().split(' ')))
# if x < c:
#     print(0)
# else:
#     ans = 0
#     for i in range(n):
#         if abs(a[i] - x) <= 3 and a[i] >= c:
#             ans += 1
#     print(ans)

# power = [2 ** i for i in range(60)]
# @lru_cache(None)
# def calc(n, op):
#     if n <= 2:
#         if op == 0: return n
#         else: return 1
#     i = power[bisect_right(power, n) - 1]
#     return calc(n - i, op ^ 1) + i // 2

def calc(n, i):
    op = 0
    t = n + 1
    while t:
        if t & 1:
            op ^= 1
        t >>= 1
    return n // 2 + ((n % 2 == 1) or (op == 0))

for _ in range(int(input())):
    a, b = list(map(int, input().split(' ')))
    if a > b or a == 1:
        c = 0
    else:
        c = 1
        x = a
        while x * a <= b:
            x *= a
            c += 1

    x, y = a, b
    x1 = y1 = x2 = y2 = 0
    while x % 5 == 0:
        x //= 5
        x1 += 1
    while x % 3 == 0:
        x //= 3
        y1 += 1
    while y % 5 == 0:
        y //= 5
        x2 += 1
    while y % 3 == 0:
        y //= 3
        y2 += 1
    d = 0
    if x == y:
        r = min(x1, x2)
        x1 -= r
        x2 -= r
        if x1 > 0:
            y1 += x1
            d += x1
        else:
            y2 += x2
            d += x2
        d += max(y1, y2) - min(y1, y2)

    f = min(a, 2) * min(b, 2)

    if b == 1 or a == 1:
        g = 0
    else:
        g = math.ceil(math.log(a) / math.log(b + 1))

    e = calc(max(a, b), 0) - calc(min(a, b) - 1, 0)

    print(c ^ d ^ e ^ f ^ g)


# print("等")
# print("我懂了")
# print("因为是你")
# print("丢铜板")
# print("还是好朋友")

C++ 解法, 执行用时: 66ms, 内存消耗: 1308K, 提交时间: 2022-06-25 17:08:58

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
int _1(int a, int b)
{
    if (a == 1) return 0;
    int ret = 0;
    int k = 1;
    while(k * a <= b)
    {
        ret++;
        k *= a;
    }
    return ret;
}
int _2(int a, int b)
{
    int ans = 0;
    while (a % 5 == 0 && b % 5 == 0) a /= 5, b /= 5;
    while (a % 5 == 0) a /= 5, a *= 3, ans++;
    while (b % 5 == 0) b /= 5, b *= 3, ans++;
    while (a % 3 == 0 && b % 3 == 0) a /= 3, b /= 3;
    while (a % 3 == 0) a /= 3, ans++;
    while (b % 3 == 0) b /= 3, ans++;
    if (a != b) return 0;
    return ans;
}
int f(int n)
{
    int x = n, cnt = 0;
    while(x)
    {
        if (x & 1) cnt++;
        x >>= 1;
    }
    return n / 2 + (cnt & 1 || n & 1);
}
int _3(int a, int b)
{
    if (a > b) swap(a, b);
    return f(b) - f(a - 1);
}
int _4(int a, int b)
{
    return min(a, 2ll) * min(b, 2ll);
}
int _5(int a, int b)
{
    if (b == 1) return 0;
    int ret = 0;
    while(a != 1)
    {
        a = (a + b) / (b + 1);
        ret++;
    }
    return ret;
}
void solve()
{
    int a, b;
    scanf("%lld%lld", &a, &b);
    printf("%lld\n", _1(a, b) ^ _2(a, b) ^ _3(a, b) ^ _4(a, b) ^ _5(a, b));
}
signed main()
{
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}

详情