BZOJ 4725: [POI2017]Reprezentacje ró?nicowe(打表暴力)

Description

给定一个数列a:
当n<=2时,a[n]=n
当n>2,且n是奇数时,a[n]=2a[n-1]
当n>2,且n是偶数时,a[n]=a[n-1]+r[n-1]
其中r[n-1]=mex(|a[i]-a[j]|)(1<=i<=j<=n-1),mex{S}表示最小的不在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],定义为repr(x)。
比如repr(17)=(6,3),repr(18)=(16,15)。
现有n个询问,每次给定一个正整数x,请求出repr(x)。

Input

第一行包含一个正整数n(1<=n<=10^5)。
接下来n行,每行一个正整数x(1<=x<=10^9),表示一个询问。

Output

输出n行,每行两个正整数p,q,依次回答每个询问。

Sample Input

2
17
18

Sample Output

6 3
16 15
思路:打了个表发现,超过57项以后,如果i为奇数那么a[i]-a[i-1]>1e9.所以超过57项以后的a[i](i是一个偶数)如果还和某个数的差小于1e9必然是和它前面的相邻奇数。
然后暴力算出来,前57项的所有数之间的差,以及他们的差都是什么。
对于查询,如果在前面57项里查到了就输出。否则的话,需要二分在表里找到最大的小于他的数并得到他是在表里的第几个。因为r[]是递增的,那么如果当前x代表了一个r[i],也就意味着前面的x-1个数都已经被别的数对所代表了。又因为表里有num个,这是前57项里有的。那么x-num就是从57项后的第几个数对有这样一个差x。那么每一个数对2个数,又因为这样的计算包含了最后差等于x的那个数对,所以答案就是(57+(x-num)*2-1,57+(x-num)*2-2).

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注