当前位置: 首页 > 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>基本信息…...

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 学习系列(三)创建和移动物体

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

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

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

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; 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…...