[LightOJ1008]Fibsieve`s Fantabulous Birthday 题解

前言

扫了一眼网上的题解，都是找规律。

估计就我一个蒟蒻在打二分。

题解

设一个" ┐"形为一层。

我们二分查找该数在那一层，然后就可以直接计算它的位置了。

代码

#include <cstdio>

int main(){

	int T, cs = 0; scanf("%d", &T);

	while (T--){

		long long x; scanf("%lld", &x);

		long long l = 1, r = 100000000, ans = 1;

		while (l <= r){

			long long mid = (l + r) / 2, tmp = (mid & 1) ? mid : mid - 1;

			long long res = tmp * tmp + !(mid & 1);

			if (res & 1)

				res = res - mid * 2 + 2;

			if (x >= res)

				l = mid + 1, ans = mid;

			else if (x < res)

				r = mid - 1;

		}

		long long tmp = (ans & 1) ? ans : ans - 1;

		long long res = tmp * tmp + !(ans & 1);

		if (res & 1)

			res = res - ans * 2 + 2;

		long long lft = x - res; printf("Case %d: ", ++cs);

		if (res & 1){

			long long posx = ans, posy = 1;

			if (lft < ans)

				posy += lft;

			else{

				posy = ans; lft -= ans - 1;

				posx -= lft;

			}

			printf("%lld %lld\n", posx, posy);

		}

		else{

			long long posx = 1, posy = ans;

			if (lft < ans)

				posx += lft;

			else{

				posx = ans; lft -= ans - 1;

				posy -= lft;

			}

			printf("%lld %lld\n", posx, posy);

		}

	}

	return 0;

}

巴特西

[LightOJ1008]Fibsieve`s Fantabulous Birthday 题解

前言

题解

代码

最新文章

热门文章