A - Farey Sequence——(筛法求欧拉函数)

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

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 <= 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

题目大意:

就是求一个F(n)的中元素的个数。


解题思路:

首先我们分析一下题目,我们一看就是关于欧拉函数的题,就是求<=b中与b互素的个数,但是我们别忘记还得加上phi(<n)的值,所以这个问题就是求欧拉函数的和的问题,然后我们如果用正常的做法也就是暴力做的话 会超时的(我试过了/笑cry),所以我们要找到更快速的方法 ——筛法,其实这个筛法就是跟素数筛差不多的,也算是又学了一个知识点

void Init()
{
    memset(phi, 0, sizeof(phi)) ;
    for(int i=2; i<MAXN; i++)
    {
        if(!phi[i])
        {
            for(int j=i; j<MAXN;j+=i )
            {
                if(!phi[j])
                    phi[j] = j ;
                phi[j] = phi[j]/i*(i-1) ;
            }
        }
    }
}

Code:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;

int phi[MAXN];
void Init()
{
    memset(phi, 0, sizeof(phi)) ;
    for(int i=2; i<MAXN; i++)
    {
        if(!phi[i])
        {
            for(int j=i; j<MAXN;j+=i )
            {
                if(!phi[j])
                    phi[j] = j ;
                phi[j] = phi[j]/i*(i-1) ;
            }
        }
    }
}
int main()
{
    Init();
    int m;
    while(cin>>m,m)
    {
        LL sum = 0;
        for(int i=2; i<=m; i++)
            sum += phi[i];
        cout<<sum<<endl;
    }
    return 0;
}


目录
相关文章
|
API 网络架构 微服务
带你读《微服务架构设计模式》之三:微服务架构中的进程间通信
成功地开发基于微服务架构的应用软件,需要掌握一系列全新的架构思想和实践。在这本独特的书籍中,微服务架构的先驱、Java 开发者社区的意见领袖 Chris Richardson 收集、分类并解释了 44 个架构设计模式,这些模式用来解决诸如服务拆分、事务管理、查询和跨服务通信等难题。本书不仅仅是一个模式目录,还提供了经验驱动的建议,以帮助你设计、实现、测试和部署基于微服务的应用程序。
14217 0
|
1月前
|
人工智能 自然语言处理 API
阿里云百炼Token Plan指南:介绍、费用、订阅、API Key 和 Base URL获取及使用全流程
阿里云百炼Token Plan团队版是AI大模型订阅服务,以Credits统一计费,支持Qwen、GLM、Kimi等12+主流文本与图像模型。提供团队管理后台、数据安全及OpenAI/Anthropic协议兼容接口,三步即可完成订阅与接入(选套餐→获API Key→配AI工具),适配Cursor、Qwen Code等30+智能编程与Agent工具。
|
2月前
|
人工智能 运维 数据可视化
阿里云百炼大模型服务平台全解析:模型推理、Agent智能体、API‑Key管理、RAG知识库与API实操完整指南
随着大模型技术走向规模化落地,开发者在搭建AI应用的时候,往往会遇到模型选型繁杂、接口标准不统一、私有知识库构建繁琐、智能体编排复杂、模型调优流程割裂等一系列现实难题。如果分散使用多款独立工具完成推理、知识库、智能体、微调评测工作,会造成多套密钥、多套接口、数据割裂、运维成本居高不下。阿里云百炼作为一站式MaaS大模型开发与应用平台,将模型广场推理、多模态能力、Agent2.0智能体、可视化工作流、RAG企业知识库、模型微调评测、MCP插件托管、CLI命令行工具全部收敛到统一平台,同时提供按量付费、Token Plan、Coding Plan多套计费订阅方案。不管是个人开发者快速验证原型项目,
661 1
|
2月前
|
人工智能 缓存 监控
阿里云Qwen3.8-Max大模型详细介绍:模型能力、功能、收费标准、内置工具及使用教程参考
本文详解阿里云通义千问Qwen3.8-Max旗舰级大模型,其为2.4万亿参数MoE架构,支持100万Token长上下文、多模态输入与完整工具调用能力,适配企业知识库、智能办公、AI编程助手等复杂场景。同时梳理华北2地域官方计费标准,配套新用户免费Tokens、Token Plan包月订阅、夜间4折优惠等多类降本方案,为开发者提供从模型体验、API接入到成本优化的完整落地指南。
|
2月前
|
人工智能 小程序 开发者
阿里云权益中心AI产品最新优惠:Qwen3.8-Flash首发尝鲜,个企双版本低至39元/月
阿里云权益中心推出“智享 AI”普惠活动,面向个人开发者与企业用户,以Qwen3.8系列新品首发为核心,构建了覆盖“尝鲜—体验—订阅—抵扣—创业扶持”的完整权益体系。活动中Qwen3.8-Max旗舰模型限时5折,低至6元/百万tokens;新用户可领取1亿+免费Tokens,同步开放Qoder CN、千问办公等多款AI Agent应用的免费体验通道。升级后的Token Plan个人版39元/月起、团队版150元/月起,搭配全模型通用抵扣低至4.5折的优惠,叠加OPC百万创新补贴计划,帮助不同规模的用户以低成本完成AI能力落地与规模化创新。
|
2月前
|
网络协议 安全 网络安全
AiWCLOUD:免备案CDN,高防CDN,不限内容,过移动屏蔽在跨境业务加速防护下
本文深度解析免备案高防CDN技术:依托境外节点规避ICP备案,实现“即开即用”;融合全球加速、T级分布式清洗与智能调度,一站式解决跨境延迟、链路不稳定及DDoS/CC攻击难题,适用于游戏出海、跨境电商、海外媒体等场景。(239字)
540 2
|
5月前
|
人工智能 自然语言处理 BI
阿里云短信服务 Skill 发布:Agent 一句话搞定群发
阿里云短信服务Skill正式发布!支持资质/签名/模板查询、短信发送、记录查询及数据统计,运营人员通过自然语言即可在AI Agent中完成全流程操作,无需技术背景,告别繁琐控制台操作,提升通知与营销短信执行效率。
715 5
|
6月前
|
数据采集 边缘计算 编解码
解析!CNC机床数据采集的几种方案优缺点对比
本文对比分析CNC机床五种主流数据采集方案:原生协议直连、PLC/IO信号、宏变量指令、外挂智能网关及屏幕图像识别,剖析其优劣与适用场景,助力企业破解兼容性差、成本高、效率低等痛点,构建高效智能的数据采集体系。
|
6月前
|
数据采集 传感器 监控
注塑机数据采集的主流方案优缺点对比
注塑机数据采集不是“一次性买卖”,而是一套递进式的技术能力升级路径。从I/O到网关、从专用授权到智能零改造,每个时机都有最适合的解法,关键是先“采得全”,然后才能“用得深”。
|
8月前
|
人工智能 编解码 自然语言处理
AI音乐狂飙:技术重塑创意边界,版权与伦理迷雾待破
全球AI加速迭代,GPT-5.2、Lyria 2、Suno V5等新模型推动AI音乐爆发式发展。《美猴亡》《Walk My Walk》等作品登顶多平台榜单,创作门槛骤降,但版权归属、伦理规范与透明度仍待破局。(239字)