POJ2478 Farey Sequence
2024-08-29 05:58:51
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 15023 | Accepted: 5962 |
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}
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
简单分析一波就知道,读入n时输出1~n的欧拉函数和即可。
飞快地敲了个暴力欧拉函数交上去,TLE。
默默打了欧拉函数表,WA。
然后把int换成long long,终于过了。
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long f[];
int n;
void phi(){
int i,j;
for(i=;i<=;i++)
if(!f[i])
for(j=i;j<=;j+=i){
if(!f[j])f[j]=j;
f[j]=f[j]/i*(i-);
}
}
int main(){
phi();
for(int i=;i<=;i++){
f[i]+=f[i-];//求前缀和
}
while(scanf("%d",&n) && n){
cout<<f[n]<<endl;
}
return ;
}
最新文章
- c#winform窗体嵌入
- Linux下安装APache
- 二、Java基础--02
- Cannot Change Opencv Webcam Setting
- Unable to execute dex: Multiple dex files define 解决方法
- iOS完美的网络状态判断工具
- chisel中pviews命令无法使用
- Raspberry 3安装docker
- LeetCode: Multiply Strings. Java
- springMVC源码分析--RequestMappingHandlerAdapter(五)
- Winsock编程基础2(Winsock编程流程)
- VO和DO转换(四) MapStruct
- 11.14 luffycity项目(6)
- Linux3.10.0块IO子系统流程(0)-- 块IO子系统概述
- oracle学习--循环语句
- EPPlus批量插入图片到Excel
- shareSDK.js web版的使用
- luoguP4466 [国际集训队]和与积 莫比乌斯反演
- 特效effects(二)
- 001——php字符串中的字符串定义
热门文章
- Vue3.0脚手架搭建
- 【图论】[USACO]控制公司 Controlling Companies
- Vue入门之v-if的使用
- 最新Python3.6从入门到高级进阶实战视频教程
- 微信小程序 input组件type属性3个值的作用
- Firebase Cloud Function 编写与部署
- JZOJ 3383. 【NOIP2013模拟】太鼓达人
- 684. Redundant Connection
- UVA - 10213 How Many Pieces of Land?(欧拉公式 + 高精度)
- Eclipse快速输出System.out.println();