Project Euler 343
题目
Fractional Sequences
For any positive integer , a
finite sequence of fractions
is defined by:
and
reduced to lowest terms for .
When reaches some integer
, the sequence stops. (That is,
when .)
Define .
For example, for :
So .
Also and
for .
Find for .
解决方案
在迭代求 的过程中,如果不发生约分,那么分子和分母之和总是相等的,这个和一开始为 。因此从一开始,在迭代的过程中,当分子 满足 时,那么就会进行约分。由于 是从 开始迭代的,因此发生约分的时候, 是 的最小质因数,设其为 。约分后,分子变成 ,分母变成 ,注意到也是一个新的分数单位,并且消去了 中最小的一个质因数 ,此时是一个新的进入了新的迭代过程。
最终, 的质因子从小到大一直被消去,直到剩下一个最大的质因子。
如果一开始 是质数时,约分便不会再发生。故 的值是 的最大质因子再减去 .
由于 , 的最大质因子要么来自 ,要么来自 。
求 的最大质因子此处不详述,使用普通筛法即可。而 则使用和 216 题类似的筛法进行筛选:令 ,如果 ,那么 ,其中 .
最终求 时将两部分结果合并即可。
代码
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); }
|