#1508. 「MtOI2019」灵梦的计算器

「MtOI2019」灵梦的计算器

题目描述

注:该背景部分改编自 disangan233 中考前买计算器的真实事件。

博丽 灵梦(Hakurei Reimu)在成功抢回八云 紫(Yakumo Yukari)用隙间偷走的香火钱后,她和依神 紫苑(Yorigami Shion)去香霖堂买东西啦!

灵梦想买一个计算器来计算神社的香火钱,但是因为香霖堂的东西太贵了,她选择使用河童重工网络(Kawashiro Nitori's Network, KNN)网购一个 Casio 计算器。

但出人意料的是,灵梦使用 KNN 买回来的 Casio 是个假货,最多只能显示整数部分(即向下取整)。

灵梦很苦恼,因为这个计算器可能会导致一些特别大的误差。所以灵梦想让拥有外界的式神(指电脑)的你帮她解决一个问题。


灵梦得到了三个实数 nnaabb4n5,5a,b104\le n\le 5,5 \le a,b \le 10),她成功地计算了 na+nbn^a+n^b,得到了一个只显示整数部分的结果。

灵梦想知道,若存在一个实数 n(n0)n'(n' \geq 0),使得 na+nb{n'}^a+{n'}^b 的结果在计算器上与 na+nbn^a+n^b 的结果显示出来完全一致时,nn' 的变化范围,即 nn' 的最大值与最小值之差。

如果你不知道如何计算 nkn^k,请使用 cmath 库的 pow() 函数,pow(n,k) 的结果即为 nkn^k 的结果。


为了提高本题的难度,灵梦给你设置了 TT 组询问。而为了在某种程度上减少你的输入和输出量,我们采用以下的代码来生成询问(代码来自河童重工):

namespace Mker
{
//  Powered By Kawashiro_Nitori
//  Made In Gensokyo, Nihon
	#define uint unsigned int
	uint sd;int op;
	inline void init() {scanf("%u %d", &sd, &op);}
	inline uint uint_rand()
	{
		sd ^= sd << 13;
		sd ^= sd >> 7;
		sd ^= sd << 11;
		return sd;
	}
	inline double get_n()
	{
		double x = (double) (uint_rand() % 100000) / 100000;
		return x + 4;
	}
	inline double get_k()
	{
		double x = (double) (uint_rand() % 100000) / 100000;
		return (x + 1) * 5;
	}
	inline void read(double &n,double &a, double &b)
	{
		n = get_n(); a = get_k();
		if (op) b = a;
		else b = get_k(); 
	}
}

在调用 Mker::init() 函数之后,你第 ii 次调用 Mker::read(n,a,b) 函数后得到的便是第 ii 次询问的 nin_i, aia_ibib_i

为了减少你的输出量,令第 ii 次询问的答案为 sis_i,你只需要输出 i=1Tsi\sum^{T}_{i=1} s_i 。如果你的答案与标准答案的绝对误差在 10210^{-2} 以内,你的答案则被视为是正确答案。

本题数据的生成采用时间复杂度远远劣于普通算法的高(da)精(bao)度(li)算法来保证精度,本题数据保证单次询问的误差小于 101010^{-10}所以本题的 SPJ 范围对于正解来说是完全足够的。


为了让你更好地做题,这里给出了关于 opop 的说明:

  • op=1op=1 时,有 a=ba=b,否则无特殊限定。

输入格式

输入共一行,包含 33 个正整数 TTseedseedopop,含义见题目描述。

输出格式

输出共一行,输出题目描述中要求输出的答案。

样例 1

500 233 0
0.00503
10000 3141592653 0
0.10166
50000 1314159 0
0.50722
50000 1314159 1
1.51676
1000000 5201314 0
10.30487

数据范围与提示

子任务

数据点编号 TT seedseed opop MkerMker
11 100\leq 100 =233=233 =0=0 5a,b104n55\leq a,b \leq 10 \qquad 4\leq n\leq 5
22 500\leq 500 2311\leq 2^{31}-1
33 1000\leq 1000
44 5000\leq 5000
55 10000\leq 10000
66 50000\leq 50000
77
88 100000\leq 100000 =1145141919=1145141919
99 2311\leq 2^{31}-1
1010 1000000\leq 1000000 =1234567890=1234567890
1111 2311\leq 2^{31}-1
1212 5000000\leq 5000000 =3141592653=3141592653
1313 2311\leq 2^{31}-1
1414
1515 10000\leq 10000 =1=1
1616 50000\leq 50000
1717
1818 100000\leq 100000 =1145141919=1145141919
1919 1000000\leq 1000000 =2718281828=2718281828
2020 5000000\leq 5000000 2311\leq 2^{31}-1

题目来源

迷途之家 2019 联赛 (MtOI2019) T2

出题人:disangan233

验题人:suwakow