洛谷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;
}