由这个式子可以得出，枚举的每一个偶数 b 都可以由更大的 a 枚举到的奇数 b 得到，所以我们就不需要枚举偶数 b 了。
但是仅凭优化枚举是不够的，其实上一步已经可以得出能够去掉枚举 b 的循环，我们只需要知道对于现在的 a 能取到的最大的 b 是多少就行了，因为只能取奇数所以这次循环能取的值就是 \frac{b_{max}}{2}+1 。
对于如何取最大的 b，通过式子推导可得 b \le \left \lfloor \sqrt{\frac{N}{2^a}} \right \rfloor，不过我在调代码时发现这里似乎需要精密处理。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int ans;
signed main(){
cin>>n;
for(int a=1;a<=n;a++){//枚举a，这里不用太在意范围，因为后面有退出判断
int p=n>>a;//相当于n/a^2，位运算优化
if(!p) break;//a到上限了
int mxc=sqrt(p);//b
if(mxc*mxc>p) mxc--;
while((mxc+1)*(mxc+1)<=p) mxc++;//这两行代码都是上文提到的精密计算
ans+=(mxc+1)/2;
}
cout<<ans;
return 0;
}
通过观察发现，每日收入可表示为关于初始值 p 的线性组合。设第 i 天收入为 A_i \cdot p + B_i，其中：
A_i 是 p 的系数，满足斐波那契递推关系。
B_i 是常数项，也满足斐波那契递推关系。
所以我们可以预处理前 20 天的系数 A_i 和 B_i
根据第 a 天收入 x = A_a \cdot p + B_a 解出 p，验证合法性后代入第 b 天公式。
下面给出正确性证明。
递推关系正确性：
基础情形：第 1、2 天系数正确
归纳假设：假设前 k-1 天成立，则第 k 天满足：
A_k = A_{k-1} + A_{k-2}
B_k = B_{k-1} + B_{k-2}
解方程正确性：
方程 x = A_a p + B_a 的解 p = (x-B_a)/A_a 必须满足：
x \ge B_a （非负性）
A_a 能整除 (x-B_a)
p \in [1, 10^6] （题目约束）
Code
#include <iostream>
using namespace std;
long long A[21], B[21]; // 存储每天的系数和常数项
void pre() {
A[1] = 1; B[1] = 0; // 第一天: p
A[2] = 1; B[2] = 1; // 第二天: p+1
for (int i = 3; i <= 20; ++i) { // 预处理后续天数
A[i] = A[i-1] + A[i-2];
B[i] = B[i-1] + B[i-2];
}
}
int main() {
pre(); // 预处理系数
int T;
cin >> T;
while (T--) {
int a, b;
long long x;
cin >> a >> x >> b;
// 获取第a天的系数和常数项
long long Aa = A[a], Ba = B[a];
long long num = x - Ba; // 解方程 Aa*p = x - Ba
// 检查p的合法性
if (num < 0 || num % Aa != 0) {
cout << "-1\n";
continue;
}
long long p = num / Aa;
if (p < 1 || p > 1e6) {
cout << "-1\n";
continue;
}
// 计算第b天收入
long long Ab = A[b], Bb = B[b];
cout << Ab * p + Bb << '\n';
}
return 0;
}
