Project Euler 343

题目

Fractional Sequences

For any positive integer $k$, a finite sequence $a_i$ of fractions $\dfrac{x_i}{y_i}$ is defined by:

$a1 = \dfrac{1}{k}$ and $a_i = \dfrac{x{i-1}+1}{y_{i-1}-1}$ reduced to lowest terms for $i>1$.

When $a_i$ reaches some integer $n$, the sequence stops. (That is, when $y_i=1$.)

Define $f(k) = n$.

For example, for $k = 20$:

$\dfrac{1}{20} \rightarrow \dfrac{2}{19} \rightarrow \dfrac{3}{18} = \dfrac{1}{6} \rightarrow \dfrac{2}{5} \rightarrow \dfrac{3}{4} \rightarrow \dfrac{4}{3} \rightarrow \dfrac{5}{2} \rightarrow \dfrac{6}{1} = 6$

So $f(20) = 6$.

Also $f(1) = 1, f(2) = 2, f(3) = 1$ and $\sum f(k^3) = 118937$ for $1 \le k \le 100$.

Find $\sum f(k^3)$ for $1 \le k \le 2\times10^6$.

解决方案

在迭代求$a_i$的过程中，如果不发生约分，那么分子和分母之和总是相等的，这个和一开始为$k+1$。因此从一开始，在迭代的过程中，当分子$x_i$满足$\gcd(x_i,k+1)>1$时，那么就会进行约分。由于$x_i$是从$1$开始迭代的，因此发生约分的时候，$x_i$是$k+1$的最小质因数，设其为$p$。约分后，分子变成$1$，分母变成$(k+1-p)/p$，注意到也是一个新的分数单位，并且消去了$k+1$中最小的一个质因数$p$，此时是一个新的进入了新的迭代过程。

最终，$k+1$的质因子从小到大一直被消去，直到剩下一个最大的质因子。

如果一开始$k+1$是质数时，约分便不会再发生。故$f(k)$的值是$k+1$的最大质因子再减去$1$.

由于$n^3+1=(n+1)(n^2-n+1)$，$n^3+1$的最大质因子要么来自$n+1$，要么来自$n^2-n+1$。

求$n+1$的最大质因子此处不详述，使用普通筛法即可。而$n^2-n+1$则使用和216题类似的筛法进行筛选：令$g(n)=n^2-n+1$，如果$p\mid g(n)$，那么$p\mid g(kp+n),p\mid g(kp-n+1)$，其中$k>0$.

最终求$f(k^3)$时将两部分结果合并即可。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6;
ll v1[N+4],b[N+4],v2[N+4];
int main(){
    for(int i=2;i<=N+1;i++){
        if(v1[i]==0){
            for(int j=i;j<=N+1;j+=i)
                v1[j]=i;
        }
    }
    for(int i=1;i<=N;i++)
        v1[i]=v1[i+1];
    for(int i=1;i<=N;i++)
        b[i]=1ll*i*i-i+1;
    for(int i=2;i<=N;i++){
        ll p=b[i];
        if(p==1) continue;
        for(ll j=i;j<=N;j+=p)
            while(b[j]%p==0)
                b[j]/=p,v2[j]=max(v2[j],p);
        for(ll j=p-i+1;j<=N;j+=p)
            while(b[j]%p==0)
                b[j]/=p,v2[j]=max(v2[j],p);
    }
    ll ans=0;
    for(int i=1;i<=N;i++)
        ans+=max(v1[i],v2[i])-1;
    printf("%lld\n",ans);
}