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

类欧几里得算法

∑ i = 0 n ⌊ a i + b c ⌋ \sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloor i=0ncai+b

推式子步骤:

分类讨论

a = 0 a=0 a=0

是个最简式子

b ≥ c b\ge c bc a ≥ c a\ge c ac

f ( a m o d c , b m o d c , c , n ) f(a\bmod c,b\bmod c,c,n) f(amodc,bmodc,c,n) 转移过来,拆一下括号就行

其他情况

M = ⌊ a n + b c ⌋ M=\lfloor\frac{an+b}{c}\rfloor M=can+b

⌊ a i + b c ⌋ = ∑ j = 1 M [ j ≤ ⌊ a i + b c ⌋ ] \lfloor \frac{ai+b}{c} \rfloor=\sum_{j=1}^M [j\le\lfloor\frac{ai+b}{c}\rfloor] cai+b=j=1M[jcai+b⌋]

  1. 拆一下后面的除号
  2. 把所有 j j j 变成 j − 1 j-1 j1
  3. 交换求和顺序
  4. 变成 i > x i>x i>x 的形式
  5. 变成 n − i ≤ x n-i\le x nix 的形式
  6. 后面直接换成 f ( c , c − b − 1 , a , m − 1 ) f(c,c-b-1,a,m-1) f(c,cb1,a,m1)
int floor_sum(int n, int c, int a, int b) {if(a==0) return (n+1)*(b/c); if(a>=c || b>=c) return floor_sum(n, c, a%c, b%c)+n*(n+1)/2*(a/c)+(n+1)*(b/c); int m=(a*n+b)/c; return n*m-floor_sum(m-1, a, c, c-b-1); 
}

对于 ∑ i = 0 n ⌊ a i + b c ⌋ 2 , ∑ i = 0 n i ⌊ a i + b c ⌋ \sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c} \rfloor}^2\,,\ \sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor i=0ncai+b2, i=0nicai+b 的求解

推的方法类似,不过会互相调用

node floor_sum(int a, int b, int c, int n) {if(a==0) return {(n+1)*(b/c)%p, (n+1)*(b/c)%p*(b/c)%p, n*(n+1)%p*i2%p*(b/c)%p}; if(a>=c || b>=c) {node t=floor_sum(a%c, b%c, c, n); int F=t.f+n*(n+1)%p*i2%p*(a/c)%p+(n+1)*(b/c)%p; int G=t.g+2*t.h%p*(a/c)%p+2*(b/c)%p*t.f%p+n*(n+1)%p*(2*n+1)%p*i6%p*(a/c)%p*(a/c)%p+(n+1)*n%p*(a/c)%p*(b/c)%p+(n+1)*(b/c)%p*(b/c)%p; int H=t.h+n*(n+1)%p*(2*n+1)%p*i6%p*(a/c)%p+n*(n+1)%p*i2%p*(b/c)%p; return {F%p, G%p, H%p}; }int m=(a*n+b)/c; node t=floor_sum(c, c-b-1, a, m-1); int F=n*m%p-t.f; int G=n*m%p*(m+1)%p-2*t.f%p-2*t.h%p-F; int H=(m*n%p*(n+1)%p-t.g-t.f)%p*i2%p; return {F%p, G%p, H%p}; 
}

相关文章:

类欧几里得算法

求 ∑ i 0 n ⌊ a i b c ⌋ \sum\limits_{i0}^{n}\lfloor \frac{aib}{c} \rfloor i0∑n​⌊caib​⌋ 推式子步骤: 分类讨论 a 0 a0 a0 是个最简式子 b ≥ c b\ge c b≥c 或 a ≥ c a\ge c a≥c 由 f ( a m o d c , b m o d c , c , n ) f(a\bmod c,b\bmod…...

c++读取和存储文件,对文件操作

#include<bits/stdc.h> using namespace std; int aa[100];//全局变量数组&#xff0c;用来接收我们从文件中读取的数据。 void zhuanhua(string a){//这个函数的作用是转化我们读取的数字&#xff0c;由于我们读取文件时//是按行读取&#xff0c;就是一下读取一行&…...

InfluxDB API -- InfluxDB笔记四

1.调试工具的安装 ApiPost (类似Postman) 2.InfluxDB v2 API 地址 官方地址: InfluxDB v2 API | InfluxDB OSS 2.7 Documentation 本地文档地址&#xff1a;host1:8086/docs 3.token认证 在web UI 的Load Data -> API Tokens里面可以复制&#xff0c;这个页面也可以创…...

数据结构 - 单链表

文章目录 目录 文章目录 一、什么是链表? 线性表: 顺序表: 二、链表的分类和实现 分类: 实现: 1.创建节点类 2.创建单链表 1.addTail(尾增) 2.删除节点值为key的第一个节点 3.插入节点(在指定位置) 4.获取链表长度 总结 前言 大家好,这篇博客给大家讲一下什么是…...

化繁为简 面板式空调网关亮相上海智能家居展 智哪儿专访青岛中弘赵哲海

面对中央空调协议不开放和智能家居协议不统一的问题&#xff0c;青岛中弘选择中央空调控制器这一细分赛道入局智能家居市场&#xff0c;始终贯彻“所有空调&#xff0c;一个网关”的产品技术理念&#xff0c;逐渐探索出一条中弘的发展路径和商业模式。 在2023年的SSHT上海国际智…...

4G版本云音响设置教程阿里云平台版本

4G版本云音响设置教程介绍 第一章 介绍了在阿里云物联网平台生一个设备使用的三元素 第二章 转换阿里云三元素 为MQTT参数&#xff0c;并下载到设备中 第三章 阿里云物联网套件协议使用说明&#xff0c;如何发送数据至设备并播放 本文目录引导 目录 4G版本云音响设置教程介…...

STM32纯中断方式发送接收数据(串行通信;keil arm5;)

除了main文件其他文件均无修改&#xff0c;正常运行--在keil arm5内...

FPGA时序分析与约束(3)——时钟不确定性

一、前言 在之前的文章中&#xff0c;我们介绍了组合电路的时序和时序电路的时序问题&#xff0c;在阅读本文章之前&#xff0c;强烈推荐先阅读完本系列之前的文章&#xff0c;因为这是我们继续学习的理论的理论基础&#xff0c;前文链接&#xff1a; FPGA时序分析与约束&…...

【Java-HDFS】使用Java操作HDFS获取HDFS指定目录下的数据量大小

Maven依赖 <dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>RELEASE</version></dependency><dependency><groupId>org.apache.logging.log4j</groupId>…...

协议定制 + Json序列化反序列化

文章目录 协议定制 Json序列化反序列化1. 再谈 "协议"1.1 结构化数据1.2 序列化和反序列化 2. 网络版计算器2.1 服务端2.2 协议定制(1) 网络发送和读取的正确理解(2) 协议定制的问题 2.3 客户端2.4 代码 3. Json实现序列化反序列化3.1 简单介绍3.2 使用 协议定制 J…...

系统架构设计师(第二版)学习笔记----系统架构概述

【原文链接】系统架构设计师&#xff08;第二版&#xff09;学习笔记----系统架构概述 文章目录 一、系统架构的定义与发展历程1.1 架构的定义1.2 架构设计的作用1.3 架构设计产生的背景1.4 软件架构的发展历程1.5 模块化开发方法1.6 模块法方法分解模块遵循的原则1.7 软件工程…...

FPGA基本算术运算

FPGA基本算术运算 FPGA基本算术运算1 有符号数与无符号数2 浮点数及定点数I、定点数的加减法II、定点数的乘除法 3 仿真验证i、加减法验证ii、乘除法验证 FPGA基本算术运算 FPGA相对于MCU有并行计算、算法效率较高等优势&#xff0c;但同样由于没有成型的FPU等MCU内含的浮点数运…...

Linux Input子系统

一、基本概念 按键、鼠标、键盘、触摸屏等都属于输入(input)设备&#xff0c;Linux 内核为此专门做了一个叫做 input子系统的框架来处理输入事件。本质属于字符设备。 1. input子系统结构如下&#xff1a; input 子系统分为 input 驱动层、input 核心层、input 事件处理层&…...

commet与websocket

commet与websocket Comet 前言 Comet是一种用于web的技术&#xff0c;能使服务器能实时地将更新的信息传送到客户端&#xff0c;而无须客户端发出请求&#xff0c;目前有两种实现方式&#xff0c;长轮询和iframe流。 实现方式 长轮询 长轮询是在打开一条连接以后保持&…...

python3 简易 http server:实现本地与远程服务器传大文件

在个人目录下创建新文件httpserver.py &#xff1a; vim httpserver.py文件内容为python3代码&#xff1a; # !/usr/bin/env python3 import datetime import email import html import http.server import io import mimetypes import os import posixpath import re import…...

Microsoft Edge 主页启动diy以及常用的扩展、收藏夹的网站

一、Microsoft Edge 主页启动diy 二、常用的扩展 1、去广告&#xff1a;uBlock Origin 2、翻译&#xff1a; 页面翻译&#xff1a;右键就有了&#xff0c;已经内置了划词翻译 3、超级复制 三、收藏夹的网站...

文末送书!谈谈原型模式在JAVA实战开发中的应用(附源码+面试题)

作者主页&#xff1a;Designer 小郑 作者简介&#xff1a;3年JAVA全栈开发经验&#xff0c;专注JAVA技术、系统定制、远程指导&#xff0c;致力于企业数字化转型&#xff0c;CSDN博客专家&#xff0c;蓝桥云课认证讲师。 本文讲解了 Java 设计模式中的原型模式&#xff0c;并给…...

视频汇聚/视频云存储/视频监控管理平台EasyCVR启动时打印starting server:listen tcp,该如何解决?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;可实现视频监控直播、视频轮播、视频录像、云存储、回放与检索、智能告警、服务器集群、语音对讲、云台控制、电子地图、H.265自动转码H.264、平台级联等。为了便于用户二次开发、调用与集成&#xff0c;…...

【Linux从入门到精通】通信 | 管道通信(匿名管道 命名管道)

本派你文章主要是对进程通信进行详解。主要内容是介绍 为什么通信、怎么进行通信。其中本篇文章主要讲解的是管道通信。希望本篇文章会对你有所帮助。 文章目录 一、进程通信简单介绍 1、1 什么是进程通信 1、2 为什么要进行通信 1、3 进程通信的方式 二、匿名管道 2、1 什么是…...

实践和项目:解决实际问题时,选择合适的数据结构和算法

文章目录 选择合适的数据结构数组链表栈队列树图哈希表 选择合适的算法实践和项目 &#x1f389;欢迎来到数据结构学习专栏~实践和项目&#xff1a;解决实际问题时&#xff0c;选择合适的数据结构和算法 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#xff1a;IT…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

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

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

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

OpenGL-什么是软OpenGL/软渲染/软光栅?

‌软OpenGL&#xff08;Software OpenGL&#xff09;‌或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式&#xff08;包括几何处理、光栅化、着色等&#xff09;&#xff0c;不依赖GPU硬件加速。这种模式通常性能较低&#xff0c;但兼容性极强&#xff0c;常用于不支持硬件加速…...