Project Euler 318

题目

$2011$ nines

Consider the real number $\sqrt 2 + \sqrt 3$.
When we calculate the even powers of $\sqrt 2 + \sqrt 3$
we get:

$\begin{aligned}
&(\sqrt 2 + \sqrt 3)^2 = 9.898979485566356 \dots \
&(\sqrt 2 + \sqrt 3)^4 = 97.98979485566356 \dots \
&(\sqrt 2 + \sqrt 3)^6 = 969.998969071069263 \dots\
&(\sqrt 2 + \sqrt 3)^8 = 9601.99989585502907 \dots \
&(\sqrt 2 + \sqrt 3)^{10} = 95049.999989479221 \dots \
&(\sqrt 2 + \sqrt 3)^{12} = 940897.9999989371855 \dots \
&(\sqrt 2 + \sqrt 3)^{14} = 9313929.99999989263 \dots \
&(\sqrt 2 + \sqrt 3)^{16} = 92198401.99999998915 \dots \
\end{aligned}$

It looks as if the number of consecutive nines at the beginning of the fractional part of these powers is non-decreasing.

In fact it can be proven that the fractional part of $(\sqrt 2 + \sqrt 3)^{2 n}$ approaches $1$ for large $n$.

Consider all real numbers of the form $\sqrt p + \sqrt q$ with $p$ and $q$ positive integers and $p < q$, such that the fractional part
of $(\sqrt p + \sqrt q)^{ 2 n}$ approaches $1$ for large $n$.

Let $C(p,q,n)$ be the number of consecutive nines at the beginning of the fractional part of $(\sqrt p + \sqrt q)^{ 2 n}$.

Let $N(p,q)$ be the minimal value of $n$ such that $C(p,q,n) \ge 2011$.

Find $\displaystyle \sum N(p,q) \,\, \text{ for } p+q \le 2011$.

解决方案

不难知道，$(\sqrt{p}+\sqrt{q})^{2n}+(\sqrt{q}-\sqrt{p})^{2n}$一定是一个整数（通过二项式定理将两个式子拆开不难证明）。

并且，如果需要得到题目中的那种收敛情况，那么就必须满足$\sqrt{q}-\sqrt{p}<1$。那么随着$n$增大，值$(\sqrt{q}-\sqrt{p})^{2n}$将无限逼近于$0$.并且，通过加法可以知道$(\sqrt{p}+\sqrt{q})^{2n}$的连续$9$的个数和$(\sqrt{p}-\sqrt{q})^{2n}$的连续$0$个数相同。

计算$(\sqrt{q}-\sqrt{p})^{2n}$的连续$0$个数不难想到使用对数解决。通过计算，$(\sqrt{q}-\sqrt{p})^{2n}$的连续$0$个数为$\left\lfloor-2n\lg (\sqrt{q}-\sqrt{p})\right\rfloor$.

那么令$M=2011$，取对数后，随着$n$增长，数$-2n\lg (\sqrt{q}-\sqrt{p})$也是线性增长的，因此可以计算出$N(p,q)$得:

$$N(p,q)=\left\lceil-\dfrac{M}{2\lg(\sqrt{q}-\sqrt{p})}\right\rceil$$

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2011,M=2011;
double sq[N+4];
int main(){
    for(int i=1;i<=N;i++)
        sq[i]=sqrt(i);
    ll ans=0;
    for(int p=1;p<=N;p++)
        for(int q=p+1;p+q<=N&&sq[q]-sq[p]<1;q++){
            double g=-log10(sq[q]-sq[p])*2;
            ans+=ceil(1.0*M/g);
        }
    printf("%lld\n",ans);
}