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个数,对于每一个数y你都需要找到一个最小x使得 ϕ ( x ) ≥ y \phi(x) \ge y ϕ(x)≥y,然后再求一个最小平和。 思路: 其实最开始以来的思路就是二分,我先进行线性筛求出每个数的欧拉函数…...

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

Java课题笔记~Maven基础知识
一、什么是Maven? Maven是专门用于管理和构建Java项目的工具。 它的主要功能有: 提供了一套标准化的项目结构提供了一套标准化的构建流程(编译,测试,打包,发布……)提供了一套依赖管理机制 …...

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

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

云原生势不可挡,如何跳离云原生深水区?
云原生是云计算领域一大热词,伴随云原生概念而来的是数字产业迎来井喷、数字变革来临、数字化得以破局以及新一波的技术红利等等。云原生即“云”原生,顾名思义是让“应用”最大程度地利用云的能力,发挥云价值的最佳路径。具体来说࿰…...

python的decimal或者叫Decimal,BigDecimal
前言 在python中进行小数计算时,很容易发生精度错误问题!!!!一定要注意!!!或者说,只要进行小数的运算都要用decimal。如:银企对账;工程计算等等在…...
Mac环境变量问题
查询环境变量 echo $PATH 查询当前使用的Shell,这里注意SHELL需要大写 echo $SHELL >>>如果输出的是/bin/zsh,说明使用的是zsh。zsh读取的个人配置文件是~/.zshrc (mac10.15.x 后对应的是~/.zprofile) >>>如果输出的是/bin/bash&…...
Shell脚本学习-Web服务监控
参考我的博客文章《Centos安装nginx》,先来安装下nginx。我按照该文档操作了一遍,还是很快就能安装好nginx的。 确认可以安装成功: [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服务,想通过web服务将它共享给其他人使用,搜了一下目前GitHub上比较热门的服务有 ChatGPT-Next-Webchatgpt-web-share 其中chatgpt-web-share支持API和PLUS账号分享两种方式,且架构为PythonJSDocker,相对比…...

【论文阅读24】Better Few-Shot Text Classification with Pre-trained Language Model
论文相关 论文标题:Label prompt for multi-label text classification(基于预训练模型对少样本进行文本分类) 发表时间:2021 领域:多标签文本分类 发表期刊:ICANN(顶级会议) 相关代…...
119、Spring容器启动流程是怎样的(配有Spring启动完整流程图)
Spring容器启动流程是怎样的 在创建Spring容器,也就是启动Spring时:首先会进行扫描,扫描得到所有的BeanDefinition对象,并存在一个Map中然后筛选出非懒加载的单例BeanDefinition进行创建Bean,对于多例Bean不需要在启动…...

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

【LeetCode】221.最大正方形
题目 在一个由 ‘0 和 ‘1 组成的二维矩阵内,找到只包含 ‘1 的最大正方形,并返回其面积。 示例 1: 输入:matrix [["1","0","1","0","0"],["1","0",&q…...
生成模型相关算法:EM算法步骤和公式推导
EM算法 引言EM算法例子及解法EM算法步骤和说明 引言 EM 算法是一种选代算法,1977 年 Dempster 等人总结提出,用于含有隐变量(hidden variable)的概率模型参数的极大似然估计,或极大后验概率估计EM算法的每次选代由两步组成:E步,求…...
Compose手势
Compose手势 本文链接: 点击 拖动 滑动 锚点 Compose Drag 拖动原理 Compose Drag 拖动原理:等待第一次按下 挂起 // UI展现出来的时候,这个while循环就已经在等待第一次按下了。事件 -> 恢复判断拖动合法性合法onDragStartonDragonDragEndforEa…...

【雕爷学编程】Arduino动手做(177)---ESP-32 掌控板2
37款传感器与执行器的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的&am…...

Ubuntu-文件和目录相关命令
🔮linux的文件系统结构 ⛳目录结构及目录路径 🧩文件系统层次结构标准FHS Filesystem Hierarchy Standard(文件系统层次结构标准) Linux是开源的软件,各Linux发行机构都可以按照自己的需求对文件系统进行裁剪,所以众多…...
显式接口实现(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>基本信息…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...