Time Limit: 1000MS | Memory Limit: 65536K | |
Description
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
Output
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 欧拉函数前缀和的更多相关文章
-
poj 2478 Farey Sequence(欧拉函数是基于寻求筛法素数)
http://poj.org/problem?id=2478 求欧拉函数的模板. 初涉欧拉函数,先学一学它主要的性质. 1.欧拉函数是求小于n且和n互质(包含1)的正整数的个数. 记为φ(n). 2. ...
-
hdu1787 GCD Again poj 2478 Farey Sequence 欧拉函数
hdu1787,直接求欧拉函数 #include <iostream> #include <cstdio> using namespace std; int n; int ph ...
-
POJ2478 Farey Sequence —— 欧拉函数
题目链接:https://vjudge.net/problem/POJ-2478 Farey Sequence Time Limit: 1000MS Memory Limit: 65536K To ...
-
poj2478 Farey Sequence (欧拉函数)
Farey Sequence 题意:给定一个数n,求在[1,n]这个范围内两两互质的数的个数.(转化为给定一个数n,比n小且与n互质的数的个数) 知识点: 欧拉函数: 普通求法: int Euler( ...
-
UVA12995 Farey Sequence [欧拉函数,欧拉筛]
洛谷传送门 Farey Sequence (格式太难调,题面就不放了) 分析: 实际上求分数个数就是个幌子,观察可以得到,所求的就是$\sum^n_{i=2}\phi (i)$,所以直接欧拉筛+前缀和 ...
-
poj2478 Farey Sequence 欧拉函数的应用
仔细看看题目,按照题目要求 其实就是 求 小于等于n的 每一个数的 欧拉函数值 的总和,为什么呢,因为要构成 a/b 然后不能约分 所以 gcd(a,b)==1,所以 分母 b的 欧拉函数值 ...
-
POJ 2478 Farey Sequence(欧拉函数前n项和)
A - Farey Sequence Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u ...
-
Farey Sequence (欧拉函数+前缀和)
题目链接:http://poj.org/problem?id=2478 Description The Farey Sequence Fn for any integer n with n >= ...
-
Poj 2478-Farey Sequence 欧拉函数,素数,线性筛
Farey Sequence Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14291 Accepted: 5647 D ...
随机推荐
-
DEDECMS之一 安装配置
一.织梦安装 1.建好数据库.数据库用户名密码以及权限 2.上传代码到服务器,根目录赋予所有权限 3.打开网址,一步步安装即可 二.配置 1.删除安装目录下的所有文件 2.系统 系统设置:配置网站基本 ...
-
xml配置文件详解
1:bean的基本属性配置: <!-- id是bean的标识符,必须唯一,如果没有配置id,name默认为标识符 如果配置了id,有配置了name,那么name为别名 name可以设置多个别名, ...
-
百度网盘,前几天刚从百度云改名过来,百度云这个名字给之前的百度开放云(同步盘用户比较小众)good
作者:黑郁金香链接:http://www.zhihu.com/question/51803053/answer/127562835来源:知乎著作权归作者所有,转载请联系作者获得授权. 在8月网盘大面积 ...
-
算法 fill
fill(vec.begin(), vec.end(),); //reset all elements to fill(vec.begin(),vec.begin + vec.size/, );//s ...
-
.NET获取英文月份缩写名(可获取其他国家)
来自: http://www.cnblogs.com/highend/archive/2010/03/16/1687126.html 今天在看本公司原有的项目代码当中 很不幸看到其中一些实现的部分代码 ...
-
codeforces 340D Bubble Sort Graph(dp,LIS)
转载请注明出处: http://www.cnblogs.com/fraud/ ——by fraud Bubble Sort Graph Iahub recently has lea ...
-
C++编程练习(16)----“排序算法 之 快速排序“
快速排序 基本思想: 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的. 算法介绍: 设要排序的 ...
-
Java 9 揭秘(10. 模块API)
Tips 做一个终身学习的人. 在本章节中,主要介绍以下内容: 什么是模块 API 如何在程序中表示模块和模块描述 如何读取程序中的模块描述 如何表示模块的版本 如何使用Module和ModuleDe ...
-
Python爬虫【解析库之pyquery】
该库跟jQuery的使用方法基本一样 http://pyquery.readthedocs.io/ 官方文档 解析库的安装 pip3 install pyquery 初始化 1.字符串初始化 htm ...
-
【问题解决:死锁】Lock wait timeout exceeded; try restarting transaction的问题
执行数据删除操作时一直超时并弹出Lock wait timeout exceeded; try restarting transaction错误 解决办法 1.先查看数据库的事务隔离级别 select ...