[洛谷P1920]成功密码

题目大意:给你n和x($nleq 10^{18},0<xleq 1$),要你求$sum_{i=1}^nfrac{x^i}{i}$。

解题思路:首先n大到要用long long存,暴力肯定是不行的。然后我们发现,当i越来越大时,答案几乎不会变,我们可以直接跳出。真的是这样吗?其实当你越加越多,会发现答案有微小的变化,然后你就WA了!

你有没有发现要求的东西和泰勒级数展开公式很相似?

根据泰勒级数展开公式$ln(1+x)=x-frac{x^2}{2}+frac{x^3}{3}-frac{x^4}{4}+...(-1leq x<1)$,把x用-x替代,发现所有项都变成负数了。

然后可以得:$-ln(1-x)=x+frac{x^2}{2}+frac{x^3}{3}+frac{x^4}{4}+...(-1leq x<1)$。

求出这个极限后,我们计算答案时,发现已经及其接近极限,则跳出循环即可,可以大大减少运算量。

但题目说x可能等于1,然而数据里是没有的(否则时限1小时都算不完)。

注意循环时求$x^i$要用快速幂,否则可能还是会TLE(貌似每次循环乘个x也能AC)。

开始我以为C++的log是以2为底的,为了求ln,用了换底公式$ln N=log N / log e$,后来才知道C++的log以e为底,相当于ln。

C++ Code:

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
#define ll long long
ll n;
double x;
double fast_pow(double x,ll i){
	double ans=1;
	while(i){
		if(i&1)ans*=x;
		x*=x;
		i>>=1;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>x>>n;
	double lim=-(log(1-x)/log(exp(1)));
	double ans=0.0;
	for(ll i=1;i<=n&&fabs(ans-lim)>1e-7;++i)ans+=fast_pow(x,i)/i;
	cout<<fixed<<setprecision(4)<<ans<<endl;
	return 0;
}
原文地址:https://www.cnblogs.com/Mrsrz/p/7363408.html