poj 2478 Farey Sequence 欧拉函数前缀和

时间:2022-12-28 19:13:07
Farey Sequence
Time Limit: 1000MS   Memory Limit: 65536K
     

Description

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 <= 106). 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

Source

POJ Contest,Author:Mathematica@ZSU

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
#define esp 1e-13
const int N=1e3+,M=1e6+,inf=1e9+,mod=;
ll p[M],ji;
bool vis[M];
ll phi[M];
ll sum[M];
void get_eular(int n)
{
ji = ;
memset(vis, true, sizeof(vis));
for(int i = ; i <= n; i++)
{
if(vis[i])
{
p[ji ++] = i;
phi[i] = i - ;
}
for(int j = ; j < ji && i * p[j] <= n; j++)
{
vis[i * p[j]] = false;
if(i % p[j] == )
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
else
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
}
int main()
{
int x,i;
get_eular(M);
memset(sum,,sizeof(sum));
for(i=;i<=1e6;i++)
sum[i]=sum[i-]+phi[i];
while(~scanf("%d",&x))
{
if(!x)break;
printf("%lld\n",sum[x]);
}
return ;
}

poj 2478 Farey Sequence 欧拉函数前缀和的更多相关文章

  1. poj 2478 Farey Sequence&lpar;欧拉函数是基于寻求筛法素数&rpar;

    http://poj.org/problem?id=2478 求欧拉函数的模板. 初涉欧拉函数,先学一学它主要的性质. 1.欧拉函数是求小于n且和n互质(包含1)的正整数的个数. 记为φ(n). 2. ...

  2. hdu1787 GCD Again poj 2478 Farey Sequence 欧拉函数

    hdu1787,直接求欧拉函数 #include <iostream> #include <cstdio> using namespace std; int n; int ph ...

  3. POJ2478 Farey Sequence —— 欧拉函数

    题目链接:https://vjudge.net/problem/POJ-2478 Farey Sequence Time Limit: 1000MS   Memory Limit: 65536K To ...

  4. poj2478 Farey Sequence &lpar;欧拉函数&rpar;

    Farey Sequence 题意:给定一个数n,求在[1,n]这个范围内两两互质的数的个数.(转化为给定一个数n,比n小且与n互质的数的个数) 知识点: 欧拉函数: 普通求法: int Euler( ...

  5. UVA12995 Farey Sequence &lbrack;欧拉函数,欧拉筛&rsqb;

    洛谷传送门 Farey Sequence (格式太难调,题面就不放了) 分析: 实际上求分数个数就是个幌子,观察可以得到,所求的就是$\sum^n_{i=2}\phi (i)$,所以直接欧拉筛+前缀和 ...

  6. poj2478 Farey Sequence 欧拉函数的应用

    仔细看看题目,按照题目要求 其实就是 求 小于等于n的 每一个数的 欧拉函数值  的总和,为什么呢,因为要构成 a/b 然后不能约分  所以 gcd(a,b)==1,所以  分母 b的 欧拉函数值   ...

  7. POJ 2478 Farey Sequence(欧拉函数前n项和)

    A - Farey Sequence Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u ...

  8. Farey Sequence (欧拉函数&plus;前缀和)

    题目链接:http://poj.org/problem?id=2478 Description The Farey Sequence Fn for any integer n with n >= ...

  9. Poj 2478-Farey Sequence 欧拉函数&comma;素数&comma;线性筛

    Farey Sequence Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 14291   Accepted: 5647 D ...

随机推荐

  1. DEDECMS之一 安装配置

    一.织梦安装 1.建好数据库.数据库用户名密码以及权限 2.上传代码到服务器,根目录赋予所有权限 3.打开网址,一步步安装即可 二.配置 1.删除安装目录下的所有文件 2.系统 系统设置:配置网站基本 ...

  2. xml配置文件详解

    1:bean的基本属性配置: <!-- id是bean的标识符,必须唯一,如果没有配置id,name默认为标识符 如果配置了id,有配置了name,那么name为别名 name可以设置多个别名, ...

  3. 百度网盘,前几天刚从百度云改名过来,百度云这个名字给之前的百度开放云(同步盘用户比较小众)good

    作者:黑郁金香链接:http://www.zhihu.com/question/51803053/answer/127562835来源:知乎著作权归作者所有,转载请联系作者获得授权. 在8月网盘大面积 ...

  4. 算法 fill

    fill(vec.begin(), vec.end(),); //reset all elements to fill(vec.begin(),vec.begin + vec.size/, );//s ...

  5. &period;NET获取英文月份缩写名&lpar;可获取其他国家&rpar;

    来自: http://www.cnblogs.com/highend/archive/2010/03/16/1687126.html 今天在看本公司原有的项目代码当中 很不幸看到其中一些实现的部分代码 ...

  6. codeforces 340D Bubble Sort Graph(dp&comma;LIS)

    转载请注明出处: http://www.cnblogs.com/fraud/          ——by fraud  Bubble Sort Graph Iahub recently has lea ...

  7. C&plus;&plus;编程练习&lpar;16&rpar;----&OpenCurlyDoubleQuote;排序算法 之 快速排序&OpenCurlyDoubleQuote;

    快速排序 基本思想: 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的. 算法介绍: 设要排序的 ...

  8. Java 9 揭秘(10&period; 模块API)

    Tips 做一个终身学习的人. 在本章节中,主要介绍以下内容: 什么是模块 API 如何在程序中表示模块和模块描述 如何读取程序中的模块描述 如何表示模块的版本 如何使用Module和ModuleDe ...

  9. Python爬虫【解析库之pyquery】

    该库跟jQuery的使用方法基本一样  http://pyquery.readthedocs.io/ 官方文档 解析库的安装 pip3 install pyquery 初始化 1.字符串初始化 htm ...

  10. 【问题解决:死锁】Lock wait timeout exceeded&semi; try restarting transaction的问题

    执行数据删除操作时一直超时并弹出Lock wait timeout exceeded; try restarting transaction错误 解决办法 1.先查看数据库的事务隔离级别 select ...