[bzoj 3858] Number Transformation

初始一个正整数x, 第i次操作将x变为i的不小于x的最小倍数, 问k次操作后得到多少. 多组数据. (1≤x,k≤10^10) 第次操作得到的数:

或者展开, 以为例:

打表发现会渐渐变成等差数列. 定义, 则

发现单减. 由于当时, , 猜测收敛于某一个值. 打表发现的确如此, 而且只需要操作约次. 按照这个思路写个程序提交就可以AC了.

但这是为什么呢? BZOJ3858 Number Transformation - Xs酱~ - 博客园

其实这个推理并不能说明问题, 因为在变大......能力有限.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
	ll x, k;
	int T = 0;
	while (scanf("%lld%lld", &x, &k) == 2 && x) {
		ll i, y = 0;
		for (i = 1; i <= k; ++i) {
			x = (x+i-1)/i;
			if (x == y) break;
			else y = x;
			x *= i;
		}
		printf("Case #%d: %lld\n", ++T, x == y ? x*k : x);
	}
	return 0;
}