CodeForces 933B A Determined Cleanup 数学

450人浏览 / 1人评论

题目链接

  • B - A Determined Cleanup
    • 给出整数p, k,问是否存在一个多项式f(x),其每项系数均为自然数且<k,且f(x)可分解为f(x)=q(x)(x+k)+p(q(x)为另一个多项式)。
    • 我们可以设q(x)=a0+a1x+a2x²+a3x³+……
    • 带入上面等式,得f(x)=(a0k+p)+(a1k+a0)x+(a2k+a1)x²+(a3k+a2)x³+……
    • 发现f(x)每项系数均为形如mk+n形式,因为每项系数均≥0且<k,所以令0≤mk+n<k,得:
    • -n/k≤m<1-n/k
    • 注意到m的范围是一个长度为1的左闭右开区间,故只要区间确定,自然数m就唯一确定。
    • 第1项时:m=a0,n=p,a0已唯一确定
    • 第2项时:m=a1,n=a0,a1已唯一确定
    • ……(下一项的n为上一项的m传递过去)
    • 以此类推,可确定多项式f(x)
    • 终止条件是什么?
    • 如果从前面传递过来的n=0,后面所有系数均为0。证明:若n=0,则0≤m<1,m=0,下一项n即为上一项的m,故下一项n=0……根据数学归纳法原理,之后所有n、m均满足n=m=0。
    • 何时无解?
    • 根据m的范围,第i项的m(i)可以写成m(i)=ceil(-n(i)/k),则下一项的n(i+1)=ceil(-n(i)/k),那么m(i+1)=ceil(-ceil(-n(i)/k)/k)。可以看出k≥2时,m的绝对值应呈递减趋势,很快会减到0,而若k=1,则m永远为常数,计算将永不停止。所以,k=1时,问题无解,只要k≠1,问题必有唯一解。
    • (以下代码是比赛中未经深刻思考写出,所以对于无解的判断是看它能否在1e5次以内计算停止。这是一个AC技巧,但是严谨的推理注定高于AC技巧。)

代码:

#include<cstdio>
using namespace std;
long long coef[(int)1e5+10];
int main()
{
	long long p;
	int k;
	scanf("%lld%d",&p,&k);
	int ind=0;
	long long tmp_p=p;
	bool ok=true;
	while(!(tmp_p>0&&tmp_p<k))
	{
		long long tmp=-(tmp_p/k);
		if(tmp>=0&&tmp_p%k)
		{
			++tmp;
		}
		coef[ind++]=tmp*k+tmp_p;
		tmp_p=tmp;
		if(ind>(int)1e5)
		{
			ok=false;
			break;
		}
	}
	if(ok)
	{
		coef[ind++]=tmp_p;
		printf("%d\n",ind);
		for(int i=0;i<ind;++i)
		{
			printf("%lld ",coef[i]);
		}
	}
	else
	{
		printf("-1");
	}
	return 0;
}

全部评论