洛谷P5515 [MtOI2019] 灵梦的计算器题解

题目链接：P5515 [MtOI2019] 灵梦的计算器

题意：

灵梦得到了 $3$ 个实数 $n,a,b$ ( $4\le n\le 5,5 \le a,b \le 10$ ) ，她成功地计算了 $n^a+n^b$，得到了一个只显示整数部分的结果。

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

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

为了提高本题的难度，灵梦给你设置了 $T$ 组询问。而为了在某种程度上减少你的输入和输出量，我们采用以下的代码来生成询问(代码来自河童重工)：
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() 函数之后，你第 $i$ 次调用 Mker::read(n,a,b) 函数后得到的便是第 $i$ 次询问的 $n_i$, $a_i$ 和 $b_i$。

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

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

输入格式：

输入共一行，包含 $3$ 个正整数 $T$，seed，op，含义见题目描述。

输出格式：

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

数据范围：

$1 \le T \le 5\times 10^6$

比较有意思的数学题，对我来说还是很难想到的。

分别记 $a_1,a_2$ 为 $n^{\prime}$ 的最小值和最大值，则有

$f(a_1)-f(a_2)<1$

我们先把图像画出来瞅一瞅（ $a_1,a_2$ 分别对应图中的 $b,a$ ）

可以发现，$A,B,C$ 三点构成的三角形满足其斜边所在直线和函数曲线近似相等

由于这道题的精度要求非常低，因此我们可以直接用把 $f^{\prime}(n)$ 看作是这条斜边的斜率，则

$a_2-a_1 = \frac{0.999}{f^{\prime}(n)}$

时间复杂度 $\mathcal{O}(T)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

namespace Mker{
#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();}
}using namespace Mker;
int T; double n,a,b,k,res;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    scanf("%d", &T); init();
    while(T--) {
        read(n, a, b);
        k = a * pow(n, a - 1) + b * pow(n, b - 1);
        res += 0.99999999 / k;
    }
    printf("%5lf\n", res);
    return 0;
}