算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理
算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理
- 欧拉函数
- AcWing 874. 筛法求欧拉函数
- 快速幂
- AcWing 875. 快速幂
- AcWing 876. 快速幂求逆元
- 扩展欧几里德(裴蜀定理)
- AcWing 877. 扩展欧几里得算法
- AcWing 878. 线性同余方程
- 中国剩余定理
欧拉函数
互质就是两个数的最大公因数只有1,体现到代码里面就是a和b互质,则b mod a = 1 mod a
(目前我不是很理解,但是可以这样理解:a和b的最大公因数是1,即1作为除数和b作为除数时,对于被除数a来说余数是一样的,即1/a的余数和b/a是一样的,即b mod a = 1 mod a
)
欧拉函数的作用是求1-n与n互质的个数
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;void get_eura(int x)
{int res = x;for (int i = 2; i <= x / i; ++ i){if (x % i == 0){//res = res * (1 - 1/i);或者res = res * (i - 1) / i;都不行,前者是浮点数1 后者会溢出res = res / i * (i - 1);while (x % i == 0){x /= i;}}}if (x > 1) res = res / x * (x - 1);cout << res << endl;
}
void solve()
{int n;cin >> n;while (n -- ){int x;cin >> x;get_eura(x);}
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T = 1;//cin >> T;while (T --) solve();return 0;
}
AcWing 874. 筛法求欧拉函数
线性筛 + 欧拉函数(有一点推公式)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
const int N = 1e6 + 10;
int primes[N], st[N], eulers[N];
int cnt;
void get_eulers(int x)
{eulers[1] = 1; for (int i = 2; i <= x; ++ i)//只是在线性筛的过程中顺便求了一下每个数的欧拉函数{if (!st[i])//1-n的质数{primes[cnt++] = i;eulers[i] = i - 1;}for (int j = 0; primes[j] <= x / i; ++ j)//1-n的合数//任何合数都含有质因数,4 = 1 * 2 * 1 * 2;{st[primes[j] * i] = 1;if (i % primes[j] == 0){eulers[i * primes[j]] = eulers[i] * primes[j];break;//其实也相当于一个else}//eulers[i * primes[j]] = eulers[i] * primes[j] / primes[j] * (primes[j] - 1);eulers[i * primes[j]] = eulers[i] * (primes[j] - 1);}}
}
void solve()
{int n;cin >> n;get_eulers(n);long long res = 0; for (int i = 1; i <= n; ++ i) res += eulers[i];cout << res;
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T = 1;//cin >> T;while (T --) solve();return 0;
}
快速幂
1 2 4 8成指数倍增长 log的时间复杂度
AcWing 875. 快速幂
long long qmi(int a, int b, int p)
{long long res = 1;while (b){if (b & 1){res = res * a % p;}a = a * (long long)a % p;b >>= 1;}return res;
}
AcWing 876. 快速幂求逆元
欧拉函数 =>费马定理 =>快速幂实现费马定理计算结果
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;long long qmi(int a, int b, int p)
{long long res = 1;while (b){if (b & 1) res = res * a % p;a = (long long)a * a % p;b >>= 1;}return res;
}
void solve()
{int n;cin >> n;while (n --){int a, p;cin >> a >> p;if (a % p == 0) cout << "impossible" << endl;else cout << qmi(a, p - 2, p) << endl;//a需要与m互质,否则a不存在乘法逆元}
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T = 1;//cin >> T;while (T --) solve();return 0;
}
扩展欧几里德(裴蜀定理)
AcWing 877. 扩展欧几里得算法
理解递归的本质:
裴蜀定理和线性同余方程的证明:
#include <cstdio>
#include <iostream>using namespace std;int exgcd(int a, int b, int &x, int &y)
{if (b == 0){x = 1, y = 0;return a;}//d就是最大公约数,本题其实用不到int d = exgcd(b, a % b, y, x);//本题的精髓/*只是为了方便更改x和y的值,如果用d = exgcd(b, a % b, x, y);最后就解得 新x = y 新y = x - a / b * y那么代码就得这么写int t = y;y = x - a / b * y;x = t;显然比只要写一句 新y -= a / b * x; 麻烦*/y -= a / b * x;return d;
}
void solve()
{int n;cin >> n;while (n -- ){int a, b, x, y;cin >> a >> b;exgcd(a, b, x, y);cout << x << " " << y << endl;}
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T = 1;//cin >> T;while (T --) solve();return 0;
}
AcWing 878. 线性同余方程
线性同余方程用扩展欧几里德定理求解
本题推导过程在上面
为什么要% m
#include <cstdio>
#include <iostream>using namespace std;int exgcd(int a, int b, int &x, int &y)
{if (b == 0){x = 1, y = 0;return a;}else//其实不用else,上面满足直接return了,上面不满足也会走到下面 {int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;}
}
void solve()
{int n;cin >> n;while (n -- ){int a, b, m, x, y;cin >> a >> b >> m;int d = exgcd(a, -m, x, y);if (b % d != 0) cout << "impossible" << endl;else cout << (long long)b / d * x % m << endl;}
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T = 1;//cin >> T;while (T --) solve();return 0;
}
中国剩余定理
相关文章:

算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理
算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理 欧拉函数AcWing 874. 筛法求欧拉函数 快速幂AcWing 875. 快速幂AcWing 876. 快速幂求逆元 扩展欧几里德(裴蜀定理)AcWing 877. 扩展欧几里得算法AcWing 878. 线性同余方程 中国剩余定理…...

ElasticSearch系列-索引原理与数据读写流程详解
索引原理 倒排索引 倒排索引(Inverted Index)也叫反向索引,有反向索引必有正向索引。通俗地来讲,正向索引是通过key找value,反向索引则是通过value找key。ES底层在检索时底层使用的就是倒排索引。 索引模型 现有索…...

【码银送书第七期】七本考研书籍
八九月的朋友圈刮起了一股晒通知书潮,频频有大佬晒出“研究生入学通知书”,看着让人既羡慕又焦虑。果然应了那句老话——比你优秀的人,还比你努力。 心里痒痒,想考研的技术人儿~别再犹豫了。小编咨询了一大波上岸的大佬ÿ…...
docker容器的设置本地时间(/etc/localtime)和本地时区(/etc/timezone)
本地时区的修改 一般情况下,我们启动docker容器时指定了环境变量: -e TZ:Asia/Ho_Chi_Minh ,容器内的时区就会变成东八区,某些软件则会读取该环境变量作为其使用的时区,该环境变量相当于"残缺版"的命令&…...

侯捷老师C++课程:内存管理
内存管理 第一讲:primitives c应用程序 c内存的基本工具 测试程序: #include <iostream> using namespace std; #include <complex> #include <ext/pool_allocator.h>int main() {// 三种使用方法void* p1 malloc(512); // 512 b…...

A股风格因子看板 (2023.09 第05期)
该因子看板跟踪A股风格因子,该因子主要解释沪深两市的市场收益、刻画市场风格趋势的系列风格因子,用以分析市场风格切换、组合风格暴露等。 今日为该因子跟踪第05期,指数组合数据截止日2023-08-31,要点如下 近1年A股风格因子检验统…...
修炼离线:(二)sqoop插入hbase 脚本(增量)
一:mysql创建表,插入数据。 二:hbase创建表。 habse shell create aa(表名),cf(列族)三:mysql_hbase脚本。 #!/bin/shmysqlHost$1 mysqlUserName$2 mysqlUserPass$3 mysqlDbName$4 myqlTbName$5 hbaseTbName$6 hbaseTbRowkey$7…...

跨平台编程开发工具Xojo 2023 Release mac中文版功能介绍
Xojo mac是一款跨平台的软件开发工具,它允许开发人员使用一种编程语言来创建应用程序,然后可以在多个操作系统上运行。Xojo 2023是Xojo开发工具的最新版本,它提供了许多功能和改进,以帮助开发人员更轻松地构建高质量的应用程序。 …...

OpenCV Series : Target Box Outline Border
角点 P1 [0] (255, 000, 000) P2 [1] (000, 255, 000) P3 [2] (000, 000, 255) P4 [3] (000, 000, 000)垂直矩形框 rect cv2.minAreaRect(cnt)targetColor roi_colortargetThickness 1targetColor (255, 255, 255)if lineVerbose:if …...

【AD】【规则设置】设置四层板
设置四层板 一般 4层板,都会把 地 和 VCC放在内层。1、使用快捷键D-K 进入层叠管理器,添加负片层添加完后,修改层名,方便辨识修改格式:属性层号 2、进入相应layer 设置网络设置GND层设置VCC层特点:在层内可…...

Linux安装JDK1.8并配置环境变量
Linux安装JDK并配置环境变量Linux安装JDK并配置环境变量Linux安装JDK并配置环境变量 一、查询已有JAVA环境版本信息 java -version 二、下载Oracle JDK安装包 https://www.oracle.com/java/technologies/downloads/archive/ 三、安装 配置JDK 以下方式适用于安装各版本JDK&…...

面向面试知识--MySQL数据库与索引
面向面试知识–MySQL数据库与索引 优化难点与面试点 什么是MySQL索引? 索引的MySQL官方定义:索引是帮助MySQL快速获取数据的数据结构。 动力节点原文: MysQL官方对于索引的定义:索引是帮助MySQL高效获取数据的数据结构。 MysQL在存储数据之…...
portainer + portainer/agent
参考链接 https://docs.portainer.io/ portainer 免费版 portainer-ce 免费版 portainer-ee 企业版 portainer-agent docker本机代理 agent 下载地址 https://download.csdn.net/download/a309450028a/87451332 portainer 下载地址 https://download.csdn…...
C# 截取字符串
在 C# 中,可以使用 Substring 方法来截取字符串的一部分。该方法有两个参数:起始索引和要截取的字符数。 以下是使用 Substring 方法截取字符串的示例: string str "Hello World"; string result str.Substring(6); // 从索引为…...

FOXBORO FBM233 P0926GX控制脉冲模块
FOXBORO FBM233 P0926GX 是一种控制脉冲模块,通常用于工业自动化和控制系统中。这个模块的主要功能是生成和控制脉冲信号,以用于执行特定的操作或控制过程。以下是可能适用于 FOXBORO FBM233 P0926GX 控制脉冲模块的一些常见特点: 脉冲生成&a…...

MySQL性能优化——MYSQL执行流程
MySQL 执行流程1-5如下图。 MySQL 的架构共分为两层:Server 层和存储引擎层, Server 层负责建立连接、分析和执行 SQL。MySQL 大多数的核心功能模块都在这实现,主要包括连接器,查询缓存、解析器、预处理器、优化器、执行器等。…...

Django:四、Djiango如何连接使用MySQL数据库
一、安装数据库第三方插件 安装下载mysql第三方插件 pip install mysqlclient 二、创建MySQL数据库 ORM可以帮助我们做两件事: 创建、修改、删除数据库中的表(不用写SQL语句),但无法创建数据库操作表中的数据(不用…...

LeetCode 热题 100(八):贪心。121. 买卖股票的最佳时机、45. 跳跃游戏 II
题目一: 121. 买卖股票的最佳时机https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 思路:因为时间复杂度O(n),所以使用贪心来做。类似双指针,一个指针记录到当前循环时最小的股票价格&…...

第N个数字
给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并返回第 n 位上的数字。 我觉得这题是哪以理解的 看这个题解 func findNthDigit(n int) int {digit : 1start : 1count : 9for n > count {n - countdigitstart start …...

【适用于电力系统和音频系统】计算信号的总谐波失真 (THD)(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...