POJ——2478 Farey Sequence(欧拉函数)

The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are 
F2 = {1/2} 
F3 = {1/3, 1/2, 2/3} 
F4 = {1/4, 1/3, 1/2, 2/3, 3/4} 
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5} 

You task is to calculate the number of terms in the Farey sequence Fn.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10 6). There are no blank lines between cases. A line with a single 0 terminates the input.

Output

For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn. 

Sample Input

2
3
4
5
0

Sample Output

1
3
5
9

题意:看那些式子也知道了,就是求1-n中有多少对互质的数,即phi[1]+phi[2]+......+phi[n]

题解:预处理出phi,然后求一个前缀和,就完事了~~

预处理主要用到了欧拉函数的性质2和性质3

欧拉函数的三个性质

性质1: 当q为质数时phi(q)=q-1

性质2: 如果i/p是p的倍数时phi(i)=phi(i/p)*p      这里p是最小质因子

性质3: 如果i/p不是p的倍数时phi(i)=phi(i/p)*(p-1)    这里p是最小质因子

性质2,性质3的用法,具体看代码:

上代码:

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAX = 1e6+520;
ll a[MAX],p[MAX],phi[MAX],sum[MAX];
bool vis[MAX];
int cnt;
void init(){
	vis[1]=vis[0]=1;
	for (int i = 2; i < MAX;i++){
		if(!vis[i]){
			p[cnt++]=i;
			a[i]=i;//a数组存的是最小质因子
		}
		for (int j = 0; j < cnt&&i*p[j] < MAX;j++){
			vis[i*p[j]]=1;
			a[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
}
void getphi(){
	phi[1]=1;
	for (int i = 2; i < MAX;i++){
		if(a[i/a[i]]==a[i]) phi[i]=phi[i/a[i]]*a[i];//性质2
		else phi[i]=phi[i/a[i]]*(a[i]-1);//性质3
	}
}
int main(){
	init();
	getphi();
	for (int i = 2; i < MAX;i++) sum[i]=sum[i-1]+phi[i];
	int n;
	while(scanf("%d",&n)&&n) printf("%lld\n",sum[n]);
	return 0;
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-25 17:55
点赞 评论 收藏
分享
机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务