Project Euler 343

Project Euler 343

题目

Fractional Sequences

For any positive integer k, a finite sequence ai of fractions xiyi is defined by:

a1=1k and ai=xi1+1yi11 reduced to lowest terms for i>1.

When ai reaches some integer n, the sequence stops. (That is, when yi=1.)

Define f(k)=n.

For example, for k=20:

120219318=162534435261=6

So f(20)=6.

Also f(1)=1,f(2)=2,f(3)=1 and f(k3)=118937 for 1k100.

Find f(k3) for 1k2×106.

解决方案

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

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

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

由于 n3+1=(n+1)(n2n+1)n3+1 的最大质因子要么来自 n+1,要么来自 n2n+1

n+1 的最大质因子此处不详述,使用普通筛法即可。而 n2n+1 则使用和 216 题类似的筛法进行筛选:令 g(n)=n2n+1,如果 pg(n),那么 pg(kp+n),pg(kpn+1),其中 k>0.

最终求 f(k3) 时将两部分结果合并即可。

代码

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
# 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);
}

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝