当前位置: 首页 > news >正文

AcWing 4575. Bi数和Phi数

文章目录

  • 题意:
  • 思路:
  • 代码

题意:

就是给你n个数,对于每一个数y你都需要找到一个最小x使得 ϕ ( x ) ≥ y \phi(x) \ge y ϕ(x)y,然后再求一个最小平和。

思路:

其实最开始以来的思路就是二分,我先进行线性筛求出每个数的欧拉函数,然后二分去找到第一个大于等于a[i]的欧拉函数,看起来确实挺合理的,但是题目要求我们找到最小满足条件的x不是最小满足条件的phi(x)。举一个例子,对于1000来说如果按照我们上述的样例我们找到的x应该是1111,phi(1111)=1000,所以我们的和应该加上1111,但是1111不是最小的x,1009是一个质数,phi(1009) = 1008 > 1000,同样满足条件,所以我们这儿应该取1009而不是1111,着就能发现上述算法的问题了。但是我们怎么去找一个满足条件的最小x呢,首先明确一点对于x一定是大于这个数本身的。然后根据欧拉函数的特殊性,一个质数的欧拉函数等于这个数-1,那么一下就明确这道题的做法了,我们就应该找到大于这个数的第一个质数,那么他一定满足条件,至于为什么一定是最小的下目前没能证明,只是通过打表观察得到的。

代码

#include<bits/stdc++.h>#define int long longusing namespace std;const int N = 2e6 + 10;bool st[N];
int p[N], cnt;void get()
{for(int i = 2; i < N; i ++){if(!st[i]) p[cnt++] = i;for(int j = 0; p[j]*i < N; j ++){st[i*p[j]] = 1;if(i % p[j] == 0) break;}}
}void solve(int op)
{int n;cin >> n;int sum = 0;for(int i = 1; i <= n; i ++){int x;cin >> x;int ip = upper_bound(p, p+cnt, x) - p;sum += p[ip];}//Case 1: 22 Xukhacout << "Case " << op << ": "  << sum << " Xukha" << endl;
}signed main()
{int _;get();cin >> _;for(int i = 1; i <= _; i ++)solve(i);return 0;
}

相关文章:

AcWing 4575. Bi数和Phi数

文章目录 题意:思路:代码 题意: 就是给你n个数&#xff0c;对于每一个数y你都需要找到一个最小x使得 ϕ ( x ) ≥ y \phi(x) \ge y ϕ(x)≥y&#xff0c;然后再求一个最小平和。 思路: 其实最开始以来的思路就是二分&#xff0c;我先进行线性筛求出每个数的欧拉函数&#xf…...

《Federated Unlearning via Active Forgetting》论文精读

文章目录 1、概述2、方法实验主要贡献框架概述 3、实验结果比较方法实验结果忘却完整性忘却效率模型实用性 4、总结 原文链接&#xff1a; Federated Unlearning via Active Forgetting 1、概述 对机器学习模型隐私的⽇益关注催化了对机器学习的探索&#xff0c;即消除训练数…...

Java课题笔记~Maven基础知识

一、什么是Maven&#xff1f; Maven是专门用于管理和构建Java项目的工具。 它的主要功能有&#xff1a; 提供了一套标准化的项目结构提供了一套标准化的构建流程&#xff08;编译&#xff0c;测试&#xff0c;打包&#xff0c;发布……&#xff09;提供了一套依赖管理机制 …...

xcode中如何显示文件后缀

xcode14.3 用不惯mac电脑真恶心&#xff0c;改个显示文件后缀找半天 1、首先双击打开xcode软件 2、此时&#xff0c;电脑左上角出现xcode字样(左上角如果看不到xcode字样&#xff0c;再次点击xcode软件弹出来就有了)&#xff0c;鼠标右键它&#xff0c;点击setting或者Prefere…...

SpringBoot使用JKS或PKCS12证书实现https

SpringBoot使用JKS或PKCS12证书实现https 生成JKS类型的证书 可以利用jdk自带的keytool工具来生成证书文件&#xff0c; 默认生成的是JKS证书 cmd命令如下: 执行如下命令&#xff0c;并按提示填写证书内容&#xff0c;最后会生成server.keystore文件 keytool -genkey tomcat…...

云原生势不可挡,如何跳离云原生深水区?

云原生是云计算领域一大热词&#xff0c;伴随云原生概念而来的是数字产业迎来井喷、数字变革来临、数字化得以破局以及新一波的技术红利等等。云原生即“云”原生&#xff0c;顾名思义是让“应用”最大程度地利用云的能力&#xff0c;发挥云价值的最佳路径。具体来说&#xff0…...

python的decimal或者叫Decimal,BigDecimal

前言 在python中进行小数计算时&#xff0c;很容易发生精度错误问题&#xff01;&#xff01;&#xff01;&#xff01;一定要注意&#xff01;&#xff01;&#xff01;或者说&#xff0c;只要进行小数的运算都要用decimal。如&#xff1a;银企对账&#xff1b;工程计算等等在…...

Mac环境变量问题

查询环境变量 echo $PATH 查询当前使用的Shell&#xff0c;这里注意SHELL需要大写 echo $SHELL >>>如果输出的是/bin/zsh&#xff0c;说明使用的是zsh。zsh读取的个人配置文件是~/.zshrc (mac10.15.x 后对应的是~/.zprofile) >>>如果输出的是/bin/bash&…...

Shell脚本学习-Web服务监控

参考我的博客文章《Centos安装nginx》&#xff0c;先来安装下nginx。我按照该文档操作了一遍&#xff0c;还是很快就能安装好nginx的。 确认可以安装成功&#xff1a; [rootvm1 sbin]# netstat -atunlp |grep 80 tcp 0 0 0.0.0.0:80 0.0.0.0:* …...

【ChatGPT】基于WSL+Docker的ChatGPT PLUS共享服务部署

最近买了ChatGPT PLUS服务&#xff0c;想通过web服务将它共享给其他人使用&#xff0c;搜了一下目前GitHub上比较热门的服务有 ChatGPT-Next-Webchatgpt-web-share 其中chatgpt-web-share支持API和PLUS账号分享两种方式&#xff0c;且架构为PythonJSDocker&#xff0c;相对比…...

【论文阅读24】Better Few-Shot Text Classification with Pre-trained Language Model

论文相关 论文标题&#xff1a;Label prompt for multi-label text classification&#xff08;基于预训练模型对少样本进行文本分类&#xff09; 发表时间&#xff1a;2021 领域&#xff1a;多标签文本分类 发表期刊&#xff1a;ICANN&#xff08;顶级会议&#xff09; 相关代…...

119、Spring容器启动流程是怎样的(配有Spring启动完整流程图)

Spring容器启动流程是怎样的 在创建Spring容器&#xff0c;也就是启动Spring时&#xff1a;首先会进行扫描&#xff0c;扫描得到所有的BeanDefinition对象&#xff0c;并存在一个Map中然后筛选出非懒加载的单例BeanDefinition进行创建Bean&#xff0c;对于多例Bean不需要在启动…...

微信公众号开发学习

申请测试号 地址 通过F12抓取体验接口权限表的HTML 解析HTML 引入pom <dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><optional>true</optional></dependency><dependency><…...

【LeetCode】221.最大正方形

题目 在一个由 ‘0 和 ‘1 组成的二维矩阵内&#xff0c;找到只包含 ‘1 的最大正方形&#xff0c;并返回其面积。 示例 1&#xff1a; 输入&#xff1a;matrix [["1","0","1","0","0"],["1","0",&q…...

生成模型相关算法:EM算法步骤和公式推导

EM算法 引言EM算法例子及解法EM算法步骤和说明 引言 EM 算法是一种选代算法&#xff0c;1977 年 Dempster 等人总结提出&#xff0c;用于含有隐变量(hidden variable)的概率模型参数的极大似然估计&#xff0c;或极大后验概率估计EM算法的每次选代由两步组成:E步&#xff0c;求…...

Compose手势

Compose手势 本文链接&#xff1a; 点击 拖动 滑动 锚点 Compose Drag 拖动原理 Compose Drag 拖动原理:等待第一次按下 挂起 // UI展现出来的时候&#xff0c;这个while循环就已经在等待第一次按下了。事件 -> 恢复判断拖动合法性合法onDragStartonDragonDragEndforEa…...

【雕爷学编程】Arduino动手做(177)---ESP-32 掌控板2

37款传感器与执行器的提法&#xff0c;在网络上广泛流传&#xff0c;其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块&#xff0c;依照实践出真知&#xff08;一定要动手做&#xff09;的理念&#xff0c;以学习和交流为目的&am…...

Ubuntu-文件和目录相关命令

&#x1f52e;linux的文件系统结构 ⛳目录结构及目录路径 &#x1f9e9;文件系统层次结构标准FHS Filesystem Hierarchy Standard(文件系统层次结构标准&#xff09; Linux是开源的软件&#xff0c;各Linux发行机构都可以按照自己的需求对文件系统进行裁剪&#xff0c;所以众多…...

显式接口实现(C# 编程指南)

接口的实现可以有多种方式,下面是C#接口实现的几种方式欢迎交流 两个接口包含签名相同的成员 如果一个类实现的两个接口包含签名相同的成员,则在该类上实现此成员会导致这两个接口将此成员用作其实现。 如下示例中,所有对 Paint 的调用皆调用同一方法。 第一个示例定义类型…...

element-ui 图片上传 及 quillEditor富文本(图片视频上传)

<template><div class"card" style"overflow: hidden; padding-bottom: 10px"><div style"padding: 20px 20px 0 20px"><span class"title_top"><span class"top_icon"></span>基本信息…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...