P5968题解
题目描述
给定一个数列 \(a\)：
- 当 \(n\le 2\) 时，\(a_n=n\)。
- 当 \(n>2\)，且 \(n\) 是奇数时， \(a_n=2\times a_{n-1}\)。
- 当 \(n>2\)，且 \(n\) 是偶数时，\(a_n=a_{n-1}+r_{n-1}\)。
其中 \(r_{n-1}= \operatorname{mex}(|a_i-a_j|)(1\le i\le j\le n-1)\)， \(\operatorname{mex} \left\{ S\right\}\) 表示最小的不在 \(S\) 集合里面的非负整数。
数列 \(a\) 的前若干项依次为：
\(1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980\)。
可以证明，对于任意正整数 \(x\)，只存在唯一一对整数 \((p,q)\) 满足 \(x=a_p-a_q\)，定义为 \(\operatorname{repr}(x)\)。
比如 \(\operatorname{repr}(17)=(6,3)\)，\(\operatorname{repr}(18)=(16,15)\)。
现有 \(n\) 个询问，每次给定一个正整数 \(x\)，请求出 \(\operatorname{repr}(x)\)。
题解
对于此类在较小项复杂且无规律的题目，通常考虑其超过值域之后的情况。
对于此题，因为存在倍增的操作，因而当 \(a\) 超过 \(10^9\) 之后就只能通过操作一得到答案。
我们考虑打出 \(a\) 在 \(10^9\) 之类的表并记录答案。对于有答案的，输出答案。反之，O(1)计算即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[]={0,1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980,2002,4004,4027,8054,8078,16156,16181,32362,32389,64778,64806,129612,129641,259282,259313,518626,518658,1037316,1037349,2074698,2074734,4149468,4149505,8299010,8299049,16598098,16598140,33196280,33196324,66392648,66392693,132785386,132785432,265570864,265570912,531141824,531141876,1062283752,1062283805};
int n,x;
struct node{
int val,u,v;
bool operator < (const node &x)const
{
return val<x.val;
}
};
vector<node>p;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
for(int i=1;i<=56;i++)
{
for(int j=1;j<i;j++)
{
p.push_back(node{a[i]-a[j],j,i});
}
}
sort(p.begin(),p.end());
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
int xx=lower_bound(p.begin(),p.end(),node{x,0,0})-p.begin();
if(p[xx].val==x)
{
cout<<p[xx].v<<" "<<p[xx].u<<'\n';
continue;
}
int num=x-xx;
cout<<num*2+56<<" "<<num*2+55<<'\n';
}
return 0;
}