Farey Sequence (素筛欧拉函数/水)题解
2024-08-24 23:06:05
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.
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
思路:
欧拉函数模板题了吧
素筛法求得欧拉函数再加起来,记得用long long
代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<cmath>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<iostream>
#include<algorithm>
#include<sstream>
#define INF 0x3f3f3f3f
#define ll long long
const int N=1e6+5;
const ll MOD=998244353;
using namespace std;
ll euler[N];
void init(){
for(int i=0;i<N;i++) euler[i]=i;
for(ll i=2;i<N;i++){
if(euler[i]==i){
for(ll j=i;j<N;j+=i){
euler[j]=euler[j]/i*(i-1);
}
}
}
for(int i=3;i<N;i++) euler[i]+=euler[i-1];
}
int main(){
init();
ll n;
while(~scanf("%lld",&n) && n){
cout<<euler[n]<<endl;
}
return 0;
}
最新文章
- 移动Web之响应式布局的探讨
- android事件处理之基于监听
- Muzli – 所有你需要的设计灵感都在这
- [置顶] iOS 名片识别代码
- tomcat原理
- HDU5437 Alisha’s Party (优先队列 + 模拟)
- Android App开之标注切图
- BZOJ 2819: Nim( nim + DFS序 + 树状数组 + LCA )
- JAVA泛型-自动包装机制不能应用于泛型数据的测试
- IsoAlgo3d - A PCF 3D Viewer for Desktop, Tablet and Smart phone
- 探索PowerShell 【十三】WMI对象
- python数据类型之集合类型
- 过滤选择器first与子元素过滤选择器first-child的区别
- 强化学习策略梯度方法之: REINFORCE 算法(从原理到代码实现)
- mongo批量操作存在更新否则插入
- Topic Model的分类和设计原则
- applicationContext.xml报错org.springframework.orm.hibernate3.LocalSessionFactoryBean not found
- XML External Entity attack/XXE攻击
- PHP发送邮件:如何自定义reply-to头部以及附件
- 毕业设计 python opencv实现车牌识别 码云地址
热门文章
- linux find 命令
- Qt计算器开发(三):执行效果及项目总结
- mysql备份工具innobackupex,xtrabackup-2.1的原理和安装
- MySQL Innodb日志机制深入分析
- ASP.NET一个页面的生命周期
- Ubuntu搭建solr搜索服务器
- 使用LinkedList模拟栈数据结构的集合
- Cobbler 自动化部署系统
- 使用gunicorn部署Flask项目
- [LeetCode] 557. Reverse Words in a String III_Easy tag: String