相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4725
神犇题解:http://blog.csdn.net/lych_cys/article/details/53455978
解题报告
这题看上去一脸不可做QwQ
前前后后想了差不多三个小时吧?
突然反应过来:从第63项开始$a(x)$就大于$10^9$了
换一句话来说:之后的每一项,只可能减去前一项才可能小于$10^9$
于是我们把前$63$项之内的拿出来暴力搞一搞
$63$项之后的,我们可以推公式推出来答案是多少
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 10000; int n,tot,vis[N],L[N],R[N],que[N]; LL f[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void insert(int w) { for (int i=w-1;i;i--) { if (abs(f[w]-f[i]) >= N) break; vis[abs(f[w]-f[i])] = 1; } } inline int query() { for (int i=1;i;i++) if (!vis[i]) return i; } inline void Get_Ans(int w, int id) { for (int j=2;j;j++) { for (int i=1;i<j;i++) { if (f[j] - f[i] == w) { L[id] = i; R[id] = j; return; } } } } inline void query(int w) { for (int j=2;j;j++) { for (int i=1;i<j;i++) { if (f[j] - f[i] == w) { cout<<j<<' '<<i<<endl; return; } } } } int main() { f[1] = 1; f[2] = 2; vis[1] = 1; for (int i=3;i<=120;i++) { if (i&1) f[i] = f[i-1] << 1; else f[i] = f[i-1] + query(); insert(i); } for (int j=2;j<=63;j++) { for (int i=1;i<j;i++) { if (f[j] - f[i] > 1e9) continue; que[++tot] = f[j] - f[i]; } } que[++tot] = (1e9) + 10; sort(que+1, que+1+tot); for (int i=1;i<tot;i++) Get_Ans(que[i], i); for (int q=read(),x,p;q;q--) { x = read(); p = lower_bound(que+1, que+1+tot, x) - que; if (que[p] == x) printf("%d %d\n",R[p], L[p]); else if (x <= 90) query(x); else printf("%lld %lld\n",(x-90-p+62)*2ll+120,(x-90-p+62)*2ll+119); } return 0; }