【原子工具】快速幂 快速乘
题幂算.一切即1
阴阳迭变积微著,叠浪层峦瞬息功
莫道浮生千万事,元知万象一归宗
文章目录
- 快速幂
- 原始快速幂(O(logn))
- 二分递归形式
- 非递归形式
- 模下意义的快速幂(O(logn))
- 二分递归形式
- 非递归形式
- 快速乘
- 龟速乘(O(logn)
- 递归式
- 非递归式
- 快速乘(光速乘)(O(1))
- 文献参考
- 总结
快速幂
原始快速幂(O(logn))
二分递归形式
#include<bits/stdc++.h>
using namespace std;#define ll long long ll q_pow(ll base,ll exp)
{if(exp == 0) return 1;ll res = q_pow(base,exp/2);if(exp & 1) return res*res*base;return res*res;
}int main()
{ll a,b;cin >> a >> b; cout << q_pow(a,b);
}
非递归形式
#include<bits/stdc++.h>
using namespace std;#define ll long long ll q_pow(ll base,ll exp)
{ll res = 1;while(exp){if(exp & 1){res = res * base; }base = base * base;exp >>= 1;}return res;
}int main()
{ll a,b;cin >> a >> b; cout << q_pow(a,b);
}
模下意义的快速幂(O(logn))
例题 : 洛谷P1226
二分递归形式
#include<bits/stdc++.h>
using namespace std;#define ll long long ll q_pow(ll base,ll exp,ll digit)
{if(exp == 0) return 1;base %= digit;ll res = q_pow(base,exp/2,digit);if(exp & 1) return (res*res)%digit*base%digit;return res*res%digit;
}int main()
{ll a,b,c;cin >> a >> b >> c; cout << a << "^" << b << " mod " << c << "=" << q_pow(a,b,c);
}
非递归形式
#include<bits/stdc++.h>
using namespace std;#define ll long longll q_pow(ll base,ll exp,ll digit)//一般来说digit写成mod多一点个人习惯
{base %= digit;ll res = 1;while(exp){if(exp & 1){res = res * base % digit; }base = base % digit * base % digit;exp >>= 1;}return res;
}int main()
{ll a,b,c;cin >> a >> b >> c; cout << a << "^" << b << " mod " << c << "=" << q_pow(a,b,c);
}
快速乘
龟速乘(O(logn)
递归式
#include <bits/stdc++.h>
using namespace std;#define ll long long
const int mod = 500;ll q_mul(ll a, ll b)
{if (b == 0) return 0;ll res = q_mul(a, b / 2);if (b & 1) return (res + res + a) % mod;//龟速乘的目的就是为了处理大数相乘使用使用modreturn (res + res) % mod;
}int main()
{ll a, b;cin >> a >> b;cout << q_mul(a, b);
}
非递归式
#include <bits/stdc++.h>
using namespace std;#define ll long long
const int mod = 500;ll q_mul(ll a, ll b)
{a % mod;ll res = 0;while (b){if (b & 1){res = (res + a) % mod;}a = (a + a) % mod;b >>= 1;}return res;
}int main()
{ll a, b;cin >> a >> b;cout << q_mul(a, b);
}
快速乘(光速乘)(O(1))
不是特别卡常数不建议使用,可能会有计算错误
#include <bits/stdc++.h>
using namespace std;#define ll long long
#define ld long double
const int mod = 1e5;ll q_mul(ll a, ll b)//非压行版
{ld temp = (ld)a * b / mod;ll q = (ll)temp * mod;return (a * b - q + mod) % mod;
}
ll q_mul(ll a, ll b)
{return (a * b - ((ll)((ld)a * b) / mod)*mod + mod) % mod;
}int main()
{ll a, b;cin >> a >> b;cout << q_mul(a, b);
}
记忆锚点 :
q = (ld)a * b / mod
(a * b − ( ll)q * mod + mod) % mod
文献参考
【OI Wiki - 快速幂】
CSDN -【谈谈知识点】快速幂&龟速乘&快速乘
总结
阴阳二进制的火花在递归中迭变,模数宇宙的涟漪于位运算里震荡。代码中的每一个移位都是对混沌的降维打击,递归栈底的return 1如同宇宙大爆炸的奇点,从虚无中诞生万千可能。新手当知:算法修炼是铸剑过程,递归与迭代是阴阳双刃,调试时的报错声恰是淬火的嘶鸣。 无论指数如何膨胀,终将拆解为二进制的星辰;纵使乘数浩如烟海,亦可化作位运算的细沙。记住,你写的不是代码,而是将混沌世界重构成数学之美的炼金术。
相关文章:
【原子工具】快速幂 快速乘
题幂算.一切即1 阴阳迭变积微著,叠浪层峦瞬息功 莫道浮生千万事,元知万象一归宗 文章目录 快速幂原始快速幂(O(logn))二分递归形式非递归形式 模下意义的快速幂(O(logn))二分递归形式非递归形式 快速乘龟速…...
Apache SeaTunnel 整体架构运行原理
概述 SeaTunnel 缘起 数据集成在现代企业的数据治理和决策支持中扮演着至关重要的角色。随着数据源的多样化和数据量的迅速增长及业务需求的快速变化,企业需要具备强大的数据集成能力来高效地处理数据。SeaTunnel通过其高度可扩展和灵活的架构,帮助企业…...
Nginx如何实现 TCP和UDP代理?
文章目录 前言 Nginx之TCP和UDP代理 工作原理示意图 配置文件和命令参数注释 基本命令 配置实例说明 TCP代理实例UDP代理实例 总结 前言 Nginx是一个高性能的HTTP和反向代理服务器,同时也支持TCP/UDP代理。在1.9.13版本后,Nginx已经支持端口转发&…...
蓝桥杯思维训练营(三)
文章目录 题目详解680.验证回文串 II30.魔塔游戏徒步旅行中的补给问题观光景点组合得分问题 题目详解 680.验证回文串 II 680.验证回文串 II 思路分析:这个题目的关键就是,按照正常来判断对应位置是否相等,如果不相等,那么就判…...
开箱即用的.NET MAUI组件库 V-Control 发布了!
之前写过挺多的MAUI Sample,其中有很多代码可以打包成组件,当组件完善到一定程度,我会把控件封装起来放到控件库中。 今天,在这个仓库建立一年零八个月后,我觉得可以考虑将其作为开源库发布。 有很多网友在观望.NET …...
动手学图神经网络(9):利用图神经网络进行节点分类 WeightsBiases
利用图神经网络进行节点分类Weights&Biases 引言 在本篇博客中,将深入探讨如何使用图神经网络(GNNs)来完成节点分类任务。以 Cora 数据集为例,该数据集是一个引用网络,节点代表文档,推断每个文档的类别。同时,使用 Weights & Biases(W&B)来跟踪实验过程和…...
【文件上传、秒传、分片上传、断点续传、重传】
文章目录 获取文件对象文件上传(秒传、分片上传、断点续传、重传)优化 获取文件对象 input标签的onchange方法接收到的参数就是用户上传的所有文件 <html lang"en"><head><title>文件上传</title><style>#inp…...
使用Pygame制作“打砖块”游戏
1. 前言 打砖块(Breakout / Arkanoid) 是一款经典街机游戏,玩家控制一个可左右移动的挡板,接住并反弹球,击碎屏幕上方的砖块。随着砖块被击碎,不仅能获得分数,还可以体验到不断加速或复杂的反弹…...
【完整版】DeepSeek-R1大模型学习笔记(架构、训练、Infra)
文章目录 0 DeepSeek系列总览1 模型架构设计基本参数专家混合模型(MoE)[DeepSeek-V2提出, DeepSeek-V3改良]多头潜在注意力(MLA)[DeepSeek-V2提出]多token预测(MTP)[DeepSeek-V3提出] 2 DeepSeek-R1-Zero及…...
深入解析:如何利用 Python 爬虫获取商品 SKU 详细信息
在电商领域,SKU(Stock Keeping Unit,库存单位)详细信息是电商运营的核心数据之一。它不仅包含了商品的规格、价格、库存等关键信息,还直接影响到库存管理、价格策略和市场分析等多个方面。本文将详细介绍如何利用 Pyth…...
【3】高并发导出场景下,服务器性能瓶颈优化方案-文件压缩
使用EasyExcel导出并压缩文件是一种高效且常见的解决方案,尤其适用于需要处理大量数据的场景。 1. 导出多个Excel文件并压缩成ZIP文件的基本流程 (1)数据准备:从数据库或其他数据源获取需要导出的数据,并将其存储在Ja…...
FPGA|生成jic文件固化程序到flash
1、单击file-》convert programming files 2、flie type中选中jic文件,configuration decive里根据自己的硬件选择,单击flash loader选择右边的add device选项 3、选择自己的硬件,单击ok 4、选中sof选项,单机右侧的add file 5、选…...
【ArcGIS_Python】使用arcpy脚本将shape数据转换为三维白膜数据
说明: 该专栏之前的文章中python脚本使用的是ArcMap10.6自带的arcpy(好几年前的文章),从本篇开始使用的是ArcGIS Pro 3.3.2版本自带的arcpy,需要注意不同版本对应的arcpy函数是存在差异的 数据准备:准备一…...
用Python获取股票数据并实现未来收盘价的预测
获取数据 先用下面这段代码获取上证指数的历史数据,得到的csv文件数据,为后面训练模型用的 import akshare as ak import pandas as pd# 获取上证指数历史数据 df ak.stock_zh_index_daily(symbol"sh000001")# 将数据保存到本地CSV文件 df.…...
Rust 所有权特性详解
Rust 所有权特性详解 Rust 的所有权系统是其内存安全的核心机制之一。通过所有权规则,Rust 在编译时避免了常见的内存错误(如空指针、数据竞争等)。本文将从堆内存与栈内存、所有权规则、变量作用域、String 类型、内存分配、所有权移动、Cl…...
Gateway路由匹配规则详解
在微服务架构中,Gateway作为请求的入口,扮演着至关重要的角色。它不仅负责路由转发,还具备安全、监控、限流等多种功能。其中,路由匹配规则是Gateway的核心功能之一,它决定了请求如何被正确地转发到目标服务。本文将详…...
项目实操:windows批处理拉取git库和处理目录、文件
初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github:codetoys,所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的,可以在任何平台上使用。 源码指引:github源…...
前端开发知识梳理 - HTMLCSS
1. 盒模型 由内容区(content)、内边距(padding)、边框(border)和外边距(margin)组成。 (1)标准盒模型(box-sizing默认值, content-boxÿ…...
nginx中的proxy_set_header参数详解
在使用 Nginx 作为反向代理服务器时,proxy_set_header 指令扮演着至关重要的角色。它允许我们自定义请求头信息,将客户端请求传递给上游服务器时,添加或修改特定的信息,从而实现更灵活的代理功能。本文将深入探讨 proxy_set_heade…...
MapReduce是什么?
MapReduce 是一种编程模型,最初由 Google 提出,旨在处理大规模数据集。它是分布式计算的一个重要概念,通常用于处理海量数据并进行并行计算。MapReduce的基本思想是将计算任务分解为两个阶段:Map 阶段和 Reduce 阶段。 Map 阶段&a…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
