题意
介绍性的问题，法雷级数(Wikipedia::法里數列 可能需要科学上网)。
简单暴力，给出一个n，求出对于1～n中每一个数，有多少个小于等于他的数与他互质，把这些数量加在一起是多少，其实就是求欧拉函数的前缀和。
思路
欧拉函数有两种得到的方法，一是使用分解因子的方法，得到单个数的欧拉函数值，时间复杂度O(sqrt(n) * log(n))。如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//only for single number circumstances long long s_phi(long long n) { long long m=(long long)sqrt(n+0.5),ans=n; for(long long i=2;i<=m;i++) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0)n/=i; } } if(n>1)ans=ans/n*(n-1); return ans; } |
可以发现这样算的话如果只求一个数的欧拉函数还是不亏的，但是如果要求非常非常多的欧拉函数，时间就会爆炸，所以我们不可以在这个题用这种方法。
第二种方法是利用欧拉函数的若干性质： 欧拉函数线性筛法详解(Lytning)，然后把素数的线性筛法和求欧拉函数结合到一起，如果要求非常多的欧拉函数，使用这种方法预处理是非常快的，而且还顺便求了素数，一石二鸟。
|
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 |
const int N = 1000000; int n; int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合 bool mark[N+10]; void getphi() { int i,j; phi[1]=1; for(i=2;i<=N;i++)//相当于分解质因式的逆过程 { if(!mark[i]) { prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。 phi[i]=i-1;//当 i 是素数时 phi[i]=i-1 } for(j=1;j<=tot;j++) { if(i*prime[j]>N) break; mark[i*prime[j]]=1;//确定i*prime[j]不是素数 if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数 { phi[i*prime[j]]=phi[i]*prime[j];break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性 } } } |
快速地得到欧拉函数值之后，前缀和什么的就是很简单的事情了。
代码
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; const int N = 1000000; int n; int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合 bool mark[N+10]; void getphi() { int i,j; phi[1]=1; for(i=2;i<=N;i++)//相当于分解质因式的逆过程 { if(!mark[i]) { prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。 phi[i]=i-1;//当 i 是素数时 phi[i]=i-1 } for(j=1;j<=tot;j++) { if(i*prime[j]>N) break; mark[i*prime[j]]=1;//确定i*prime[j]不是素数 if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数 { phi[i*prime[j]]=phi[i]*prime[j];break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性 } } } long long phisum[1000006]; int main(){ getphi(); for (int i = 2; i <= 1000000; i++) { phisum[i] = phi[i] + phisum[i-1]; } int q; while (cin >> q && q) { cout << phisum[q] << endl; } return 0; } |
August 22, 2015
[…] 然而这个题的精髓并不是这么水过去的，这个题其实是一个包装过了的法雷级数(Wikipedia::法里数列 可能需要科学上网)，如果试着一圈圈地写一下斜率，就会发现每一圈正好满足分子和分母互质的特性，每一圈的个数其实是欧拉函数值，整个答案是欧拉函数前缀和。所以我们就有了O(n)，的处理方法，详细的可以看这个题POJ 2478 Farey Sequence。 […]