CodeForces 1242D Number Discovery

CodeForces 1242D Number Discovery

https://codeforces.com/contest/1242/problem/D

(T) 组数据,每组给出 (n,k) .现在要用如下方式生成一个无限大的序列 (s)

(s) 初始为空,重复一下步骤

• 选择前 (k) 个不曾出现在 (s) 中的正整数 (u_1,u_2,cdots,u_k)
• 将 (u_1,u_2,cdots,u_k,sum_{i=1}^k u_i) 按此顺序加入 (s)

易证所有正整数只会在 (s) 中出现一次,求 (n) 在 (s) 中的编号.

(1 le k le 10^6,1 le n le 10^{18})

Tutorial

称所有以 (sum u_i) 的形式加入 (s) 的数为non-self数,以 (u_i) 的形式加入 (s) 的为self数.

观察发现,若设 (I_i=[i(k^2+1)+1,(i+1)(k^2+1)]) ,即 (k^2+1) 的大小的每一块,那么每个 (I_i) 中,有且只有一个non-self数.

考虑归纳法,对于 (I_0) 它显然只包含一个non-self数 (dfrac 12k(k+1)) .那么考虑对于 (I_i) 中的 (k^2) 个self数组成的 (k) 次求和

[sum_{j=1}^k (i cdot (k^2+1)+tk+j) +offset = (k cdot i+t)(k^2+1) + dfrac {k(k+1)}{2}-t+offset ]

其中 (t) 表示这是第 (t) 组求和, (offset) 表示 (I_i) 中的non-self数的影响,显然有 (0 le offset le k) ,所以发现其实第 (t) 组的求和决定了 (I_{i cdot k +t}) 中的non-self数.

所以可以如此递归求解,得到 (n) 的所属的 (I_i) 的non-self数 (x) ,如果这个数为 (n) ,则答案为 ((i+1)(k+1)) ,否则设 (p=n-i-(x<n)) 表示 (n) 之前的self数,则答案为 (p+lfloor dfrac {p-1}k floor) .

Code

https://codeforces.com/contest/1242/submission/77266243

#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char nc()
{
	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f;
}
typedef long long ll;
ll n,k;
ll B;
ll I0;
int T;
ll I(ll x)
{
	if(x==0) return I0;
	ll i=x/k,t=x%k;
	ll Ii=I(i);
	ll l=i*B+t*k+1;
	ll r=l+k-1;
	ll Ix=(l+r)*(r-l+1)/2;
	if(Ii<=l) Ix+=k;
	else if(Ii<=r) Ix+=r-Ii+1;
	return Ix;
}
int main()
{
	read(T);
	for(int kase=1;kase<=T;++kase)
	{
		read(n),read(k);
		B=k*k+1;
		I0=k*(k+1)/2;
		ll i=(n-1)/B;
		ll Ii=I(i);
		if(n==Ii) printf("%I64d
",(i+1)*(k+1));
		else
		{
			ll p=n-i-(Ii<n);
			printf("%I64d
",p+(p-1)/k);
		}
	}
	return 0;
}