HDU The Boss on Mars(容斥原理)

题目大意:
ACM 有 n 名员工,现在是他们从老板那里拿薪水的时候了。所有员工都从 1 到 n 编号。原因不明,如果员工的工作编号是 k,他今年可以获得 k^4 Mars 美元。所以为 ACM 工作的员工非常富有。
因为员工人数太多,ACM 的老板必须分配太多的钱,他想明年解雇工作号与 n 共质的人。现在老板想知道解雇后他会节省多少钱。
思路:先求出1~n的每个数的四次方的求和,然后再减去n的因子的四次方的求和。把n的因子的质因子找出来,然后使用容斥原理(我容斥原理用的方法是二进制)去做。
求和公式: ( 搜来的 )
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int vis[10005],prime[10005];
int ksm(int x,int y){int ans=1;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;
}
int fun(int x){//求 a ^ 4 的前 x 项和return (x*(x+1)%mod*(2*x+1)%mod*(3*x*x%mod+3*x%mod-1+mod)%mod)%mod*ksm(30,mod-2)%mod;
}
signed main(){int cnt=0;for(int i=2;i<=10000;i++){//埃式筛求 1 ~ 10000 之间的素数 if(vis[i]) continue;prime[cnt++]=i;for(int j=i*2;j<=10000;j+=i){vis[j]=1;}}int _;cin >> _;while(_--){int n;cin >> n;vector<int> v;//存质因数 int m=n;for(int i=0;i<cnt;i++){//挑选 n 的质因子 if(m%prime[i]==0){v.push_back(prime[i]);while(m%prime[i]==0) m/=prime[i];}}if(m>1) v.push_back(m);//若不为 1 ,说明还留下 1 个质因子 int ans=fun(n),res=0;for(int i=1;i<(1<<v.size());i++){int num=1,sum=0;//num 代表几种不同质因子组成的最小因子 ,sum 代表质因子的个数 for(int j=0;j<v.size();j++){ if((i>>j)&1) sum++,num*=v[j];}int tmp=num*num%mod*num%mod*num%mod*fun(n/num);//求出 num 的倍数(不大于 n ) 的四次方之和。将这个最小因子的四次方之和提出,剩下的就是 a^4 的前几项和//例如:2^4 + 4^4 + 6^4 + 8^4 = 2^4 * ( 1^4 + 2^4 + 3^4 + 4^4 )if(sum%2) res=(res+tmp)%mod;//容斥原理 else res=(res-tmp)%mod;}ans=((ans-res)%mod+mod)%mod;cout << ans << endl;}return 0;
}
相关文章:
HDU The Boss on Mars(容斥原理)
题目大意: ACM 有 n 名员工,现在是他们从老板那里拿薪水的时候了。所有员工都从 1 到 n 编号。原因不明,如果员工的工作编号是 k,他今年可以获得 k^4 Mars 美元。所以为 ACM 工作的员工非常富有。 因为员工人数太多,…...
nnUnet 大模型学习笔记(续):训练网络(3d_fullres)以及数据集标签的处理
目录 1. 数据集处理 1.1 实现脚本 1.2 json文件 2. 设置读取路径 2.1 设置路径 2.2 数据集转换 2.3 数据集预处理 2.4 训练(3d_fullres) 3. 训练结果展示 关于nnUnet 数据集的处理和环境搭建,参考上文:第四章:nnUnet大模…...
Java中的数据结构与集合源码
目录 一、数据结构 1.1 数据结构概念 1.2 研究对象 1.3 常见存储结构 1.3.1 数组 1.3.2 链表 1.单向链表 2.双向链表 1.3.3 二叉树 1.3.4 栈(FILO,先进后出) 1.3.5 队列(FIFO,先进先出) 二、集合…...
Java应用程序的测试覆盖率之设计与实现(三)-- jacoco cli 客户端
一、背景 上文已把覆盖率数据采集好了,并提供远程连接的tcp地址及端口。 jacoco cli文档jacoco cli jar包 jacococli.jar 我下载好了,放在github工程里。 本文主要是介绍如何使用jacoco cli 客户端读取并生成覆盖率报告。 二、使用 1、dump覆盖率统…...
Deepin V23 / 统信UOS 下安装与配置 tftp
几个月前,我将开发系统从 ubuntu 切换到 Deepin,当时写过一篇文章《使用国产操作系统作为开发系统》。几个月下来,没有感觉有什么不适应,Ubuntu 能做的事情,在 Deepin 上都能做。而且有 UOS 应用商店的加持,…...
java基础学习:定时任务常见实现方式
一、Timer解析 TaskQueue:小顶堆,存放timeTask。 TimerThread:任务执行线程 死循环不断检查是否有任务需要开始执行,有就执行它。始终是一个线程在执行。 单线程执行任务,任务有可能相互阻塞: schedul…...
句柄是什么?有什么用?举例说明
在C#编程中,“句柄”(Handle)是一个与操作系统资源相关联的标识符。句柄是一个指针或者索引,用于在程序代码中引用系统资源,如窗口、文件、线程等。由于直接操作这些资源非常危险且复杂,操作系统提供句柄作…...
Jenkins学习笔记
Jenkins学习笔记 NumTitleComments1官网 官方网站 中文文档2基础Jenkins基础3groovy1.groovy语法 2.groovy 入门4pipelinepipeline基本语法介绍5Github actiongithub action6Shared library1 2...
AI 解读软考高级操作系统顺序存取、直接存取、随机存取、相联存取的区别
这几个术语描述了不同类型的存储方式,它们涉及数据存取的顺序和灵活性。为了更好地理解,我们可以先通过生活中的例子来感受这些概念。 生活化例子 1. 顺序存取: 想象你在看一盘录像带(比如老式的VHS录像带)。如果你想…...
STM32烧写准备
目录 一.安装stlink驱动二.烧写器固件升级三.安装烧写程序四.进行测试1.流水灯 五.出现的问题1.升级固件问题2.测试时连接问题 一.安装stlink驱动 amd64是用在64位的,x86用在32位;双击运行即可 出现以下情况表示安装完成当连接上STM32开发板时ÿ…...
为Windows Terminal 配置zsh + Oh-My-Zsh!
参考: 为Windows Terminal 配置zsh Oh-My-Zsh! [非WSL] https://zhuanlan.zhihu.com/p/625583037 Package: zsh - MSYS2 Packages 安装配置 1、安装 Windows Terminal(必须) Method 1: 打开 Microsoft Store,搜索 “Windows Terminal”。点击 “…...
RNN、LSTM 与 Bi-LSTM
一. RNN 循环神经网络(Recurrent Neural Network, RNN)是深度学习领域一类具有内部自连接的神经网络能够学习复杂的矢量到矢量的映射。 最大特点:前面的序列数据可以用作后面的结果预测中。 一个简单的循环神经网络结构,其结构包…...
第一性原理
第一性原理是指从最基本的真理出发,分析和推导复杂现象或问题,不依赖于传统的假设或经验,而是从根本的原则出发进行思考。 将复杂问题拆解为更小的部分,逐一分析。在理解了这些基本部分的基础上,再进行组合和构建&…...
DOM NamedNodeMap 接口详解
DOM NamedNodeMap 接口详解 引言 在文档对象模型(DOM)中,NamedNodeMap 接口提供了一种方式来操作元素的属性集合。它是一种特殊的 NodeList,其中的每个节点都有一个名称和值。本文将详细介绍 NamedNodeMap 接口,包括其属性、方法和使用场景。 NamedNodeMap 接口概述 N…...
EasyExcel自定义下拉注解的三种实现方式
文章目录 一、简介二、关键组件1、ExcelSelected注解2、ExcelDynamicSelect接口(仅用于方式二)3、ExcelSelectedResolve类4、SelectedSheetWriteHandler类 三、实际应用总结 一、简介 在使用EasyExcel设置下拉数据时,每次都要创建一个SheetWr…...
Burp Suite Professional 2024.9 for macOS x64 ARM64 - 领先的 Web 渗透测试软件
Burp Suite Professional 2024.9 for macOS x64 & ARM64 - 领先的 Web 渗透测试软件 世界排名第一的 Web 渗透测试工具包 请访问原文链接:https://sysin.org/blog/burp-suite-pro-mac/ 查看最新版。原创作品,转载请保留出处。 作者主页࿱…...
使用Mock库进行依赖注入的实用指南
使用Mock库进行依赖注入的实用指南 在现代软件开发中,测试是确保代码质量的重要环节。尤其是在进行单元测试时,依赖注入(Dependency Injection, DI)是一种常用的设计模式,它可以帮助我们更好地管理依赖关系,提高代码的可测试性。本文将深入探讨如何使用Python的unittest…...
nosql课本习题
nosql题目 1. 文档数据库相比其他 NoSQL 的突出优势和特点是什么? 答案: 文档数据库的突出优势在于它的灵活性和可扩展性。不同于传统的关系型数据库,文档数据库允许存储半结构化和非结构化数据,每个文档可以有不同的字段&#x…...
springboot 3.2.5集成spring security 只放行get请求,其他请求403
环境配置 jdk 17 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>3.2.5</version><relativePath/> <!-- lookup parent from repository --></…...
【linux】麒麟v10安装ELKB(ARM架构)
安装elasticsearch 创建目录 #放安装软件的位置 mkdir -pv /software#安装elasticsearch目录 mkdir -pv /usr/local/elasticsearch#安装kibana目录 mkdir -pv /usr/local/kibana 解压elasticsearch tar -zxvf elasticsearch-8.8.1-linux-aarch64.tar.gz -C /usr/local/elast…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
从零手写Java版本的LSM Tree (一):LSM Tree 概述
🔥 推荐一个高质量的Java LSM Tree开源项目! https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree,专为高并发写入场景设计。 核心亮点: ⚡ 极致性能:写入速度超…...
