C++(g++ 7.5.0) 解法, 执行用时: 1762ms, 内存消耗: 89344K, 提交时间: 2023-04-08 22:53:39

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll fib[95];
int len;

map<ll, ll> mp;

ll solve(ll n) {
	if (n <= 0) return 0;
	if (mp.count(n)) return mp[n];
	ll ans = 0;
	for (int i = len; i >= 1; i--) {
		if (n >= fib[i]) {
			if ((n - fib[i] + 1) & 1) ans ^= fib[i];
			return mp[n] = ans ^ solve(n - fib[i]) ^ solve(fib[i] - 1);
		}
	}
	return 0;
}

int main() {
	fib[1] = 1, fib[2] = 2;
	for (int i = 3; i <= 90; ++ i) {
		fib[i] = fib[i - 1] + fib[i - 2];
		if (fib[i] > 1e18) {
			len = i;
			break;
		}
	}
	int T;
	scanf("%d", &T);
	while (T--) {
		ll l, r;
		scanf("%lld%lld", &l, &r);
		printf("%lld\n", solve(r) ^ solve(l - 1));
	}
	return 0;
}

C++ 解法, 执行用时: 2032ms, 内存消耗: 87928K, 提交时间: 2021-10-18 14:37:55

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll t,fib[109];
map <ll,ll> f;
inline ll solve(ll x)
{
	if(f.find(x)!=f.end()) return f[x];
	ll v=*(upper_bound(fib+1,fib+87+1,x)-1);
	f[x]=solve(v-1)^solve(x-v);
	if((x-v+1)&1) f[x]^=v;
	return f[x];
}
int main()
{
	fib[1]=1,fib[2]=2;
	for(int i=3;i<=87;i++) fib[i]=fib[i-1]+fib[i-2];
	scanf("%lld",&t);
	f[0]=0;
	ll l,r;
	while(t--)
	{
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",solve(l-1)^solve(r));
	}
	return 0;
}