Loj 6690 灵梦的计算器

Posted on | Views:

牛顿迭代求解方程.

令 $k=\lfloor n^a+n^b\rfloor,f(x)=x^a+x^b$ ,那么就是要求解 $f(n_0)=k$ 与 $f(n_1)=k+1$ 两个方程.

直接二分精度不够,利用牛顿迭代,这两个根都在 $n$ 附近,取 $x_0=n$ ,迭代一次精度即可达到要求.

发现常数比较大,跑不过去,其实并不需要把这两个根分别求出来,只需要求得两根之差,加入贡献即可.
$$
\begin{aligned}
n_0&=n-\frac{f(n)-k}{f’(n)} \\
n_1&=n-\frac{f(n)-k-1}{f’(n)} \\
n_1-n_0&=\frac {1} {f’(n)}=\frac {1} {an^{a-1}+bn^{b-1}}
\end{aligned}
$$
发现这个贡献与 $k$ 无关,于是每次询问可以少调用 $4$ 次 $pow$ 函数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
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(); 
	}
}
int main()
{
	int T=read();
	Mker::init();
	double n,a,b,k,ans=0;
	while(T--)
	{
		Mker::read(n,a,b);
		ans+=1/(a*pow(n,a-1)+b*pow(n,b-1));
	}
	printf("%.3lf\n",ans);
	return 0;
}