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

算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理

算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理

  • 欧拉函数
    • 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. 快速幂求逆元 扩展欧几里德&#xff08;裴蜀定理&#xff09;AcWing 877. 扩展欧几里得算法AcWing 878. 线性同余方程 中国剩余定理…...

ElasticSearch系列-索引原理与数据读写流程详解

索引原理 倒排索引 倒排索引&#xff08;Inverted Index&#xff09;也叫反向索引&#xff0c;有反向索引必有正向索引。通俗地来讲&#xff0c;正向索引是通过key找value&#xff0c;反向索引则是通过value找key。ES底层在检索时底层使用的就是倒排索引。 索引模型 现有索…...

【码银送书第七期】七本考研书籍

八九月的朋友圈刮起了一股晒通知书潮&#xff0c;频频有大佬晒出“研究生入学通知书”&#xff0c;看着让人既羡慕又焦虑。果然应了那句老话——比你优秀的人&#xff0c;还比你努力。 心里痒痒&#xff0c;想考研的技术人儿~别再犹豫了。小编咨询了一大波上岸的大佬&#xff…...

docker容器的设置本地时间(/etc/localtime)和本地时区(/etc/timezone)

本地时区的修改 一般情况下&#xff0c;我们启动docker容器时指定了环境变量&#xff1a; -e TZ:Asia/Ho_Chi_Minh &#xff0c;容器内的时区就会变成东八区&#xff0c;某些软件则会读取该环境变量作为其使用的时区&#xff0c;该环境变量相当于"残缺版"的命令&…...

侯捷老师C++课程:内存管理

内存管理 第一讲&#xff1a;primitives c应用程序 c内存的基本工具 测试程序&#xff1a; #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股风格因子&#xff0c;该因子主要解释沪深两市的市场收益、刻画市场风格趋势的系列风格因子&#xff0c;用以分析市场风格切换、组合风格暴露等。 今日为该因子跟踪第05期&#xff0c;指数组合数据截止日2023-08-31&#xff0c;要点如下 近1年A股风格因子检验统…...

修炼离线:(二)sqoop插入hbase 脚本(增量)

一&#xff1a;mysql创建表&#xff0c;插入数据。 二&#xff1a;hbase创建表。 habse shell create aa(表名),cf(列族)三&#xff1a;mysql_hbase脚本。 #!/bin/shmysqlHost$1 mysqlUserName$2 mysqlUserPass$3 mysqlDbName$4 myqlTbName$5 hbaseTbName$6 hbaseTbRowkey$7…...

跨平台编程开发工具Xojo 2023 Release mac中文版功能介绍

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

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层板&#xff0c;都会把 地 和 VCC放在内层。1、使用快捷键D-K 进入层叠管理器&#xff0c;添加负片层添加完后&#xff0c;修改层名&#xff0c;方便辨识修改格式&#xff1a;属性层号 2、进入相应layer 设置网络设置GND层设置VCC层特点&#xff1a;在层内可…...

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索引&#xff1f; 索引的MySQL官方定义&#xff1a;索引是帮助MySQL快速获取数据的数据结构。 动力节点原文&#xff1a; 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# 中&#xff0c;可以使用 Substring 方法来截取字符串的一部分。该方法有两个参数&#xff1a;起始索引和要截取的字符数。 以下是使用 Substring 方法截取字符串的示例&#xff1a; string str "Hello World"; string result str.Substring(6); // 从索引为…...

FOXBORO FBM233 P0926GX控制脉冲模块

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

MySQL性能优化——MYSQL执行流程

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

Django:四、Djiango如何连接使用MySQL数据库

一、安装数据库第三方插件 安装下载mysql第三方插件 pip install mysqlclient 二、创建MySQL数据库 ORM可以帮助我们做两件事&#xff1a; 创建、修改、删除数据库中的表&#xff08;不用写SQL语句&#xff09;&#xff0c;但无法创建数据库操作表中的数据&#xff08;不用…...

LeetCode 热题 100(八):贪心。121. 买卖股票的最佳时机、45. 跳跃游戏 II

题目一&#xff1a; 121. 买卖股票的最佳时机https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 思路&#xff1a;因为时间复杂度O&#xff08;n&#xff09;&#xff0c;所以使用贪心来做。类似双指针&#xff0c;一个指针记录到当前循环时最小的股票价格&…...

第N个数字

给你一个整数 n &#xff0c;请你在无限的整数序列 [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代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

kubernetes(k8s)PVC

概念 PVC 的全称是&#xff1a;PersistentVolumeClaim&#xff08;持久化卷声明&#xff09;&#xff0c;PVC 是用户存储的一种声明&#xff0c;PVC 和 Pod 比较类似&#xff0c;Pod 消耗的是节点&#xff0c;PVC 消耗的是 PV 资源&#xff0c;Pod 可以请求 CPU 和内存&#x…...

Android ANR问题触发机制

1 Anr类型 ​ Anr一般有四种类型。 1.1 input dispatching timeout ​ 主要时按键或触摸屏事件在5s内没有响应。这个时间在ActivityManagerService中定义。 C:\Users\wangjie\AppData\Local\Android\Sdk\sources\android-32\com\android\server\am\ActivityManagerService.…...

解决jupyter找不到虚拟环境的问题

解决jupyter找不到虚拟环境的问题 使用jupyter只能使用base环境&#xff0c;不能找到自己创建的虚拟环境。如下图&#xff0c;显示的默认的虚拟环境base的地址。 如何解决这个问题&#xff1f;需要两个步骤即可 1 . 在base环境中安装nb_conda_kernels这个库 activate base c…...

Unity丨移动相机朝向目标并确定目标在摄像机可视范围内丨摄像机注释模型丨摄像机移动丨不同尺寸模型优化丨

文章目录 问题描述功能展示技术细节小结 问题描述 本文提供的功能是摄像机朝向目标移动&#xff0c;并确定整个目标出现在摄像机视角内&#xff0c;针对不同尺寸的模型优化。 功能展示 提示&#xff1a;这里可以添加技术名词解释 技术细节 直接上代码 using UnityEngine;…...

排序算法:归并排序(递归和非递归)

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关排序算法的相关知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通…...

数据可视化

一、Flask介绍 #通过访问路径&#xff0c;获取用户的字符串参数 app.route(/user/<name>) def welcome(name):return "你好&#xff0c;%s"%nameapp.route(/user/<int:id>) def welcome2(id):return "你好&#xff0c;%d号的会员"%id能够自动…...

Go并发可视化解释 – select语句

上周&#xff0c;我发布了一篇关于如何直观解释Golang中通道&#xff08;Channel&#xff09;的文章。如果你对通道仍然感到困惑&#xff0c;请先查看那篇文章。 Go并发可视化解释 — Channel 作为一个快速复习&#xff1a;Partier、Candier和Stringer经营着一家咖啡店。Partie…...

http的网站进行访问时候自动跳转至https

通常情况下我们是用的都是http的路径&#xff0c;对于https的使用也很少&#xff0c;但是随着https的普及越来越多的域名访问需要用到https的&#xff0c;这个我们就演示怎么设置在我们对一个http的网站进行访问时候自动跳转至https下。 用到的工具及软件: 系统&#xff1a;wi…...

realloc

目录 前提须知&#xff1a; 函数介绍&#xff1a; 函数原型&#xff1a; 使用realloc&#xff1a; realloc在调整内存空间的是存在两种情况/使用realloc为扩大空间的两种情况 1.是剩下的没有被分配的空间足够 2 .剩下没有被分配的空间不够了 注意事项&#xff1a; rea…...

Windows AD域使用Linux Samba

Windows AD域使用Linux Samba 1. 初始化配置 1.1 初始化配置 配置服务器名 hostnamectl set-hostname samba.sh.pana.cnhosts文件配置,确保正常解析到本机和域控 [rootcentos7 ~]# cat /etc/hosts 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.loc…...

中国公路建设招标网站/江苏网站seo

由于获取Calendar实例&#xff0c;是根据当前时间戳来获取的&#xff0c;故在获取特定的日期的开始时间时&#xff0c;毫秒数一般不为0&#xff0c;这时候可以手动设置为0。可以参见这位仁兄的代码&#xff1a; https://blog.csdn.net/nihaoa50/article/details/70768091...

wordpress文章调用插件/求职seo服务

简单面试题&#xff0c;但是容易忘记 1.为什么等待和通知是在 Object 类而不是 Thread 中声明的&#xff1f; **1) wait 和 notify 不仅仅是普通方法或同步工具&#xff0c;更重要的是它们是 Java 中两个线程之间的通信机制。**对语言设计者而言, 如果不能通过 Java 关键字(例…...

做网站的资料修改/seo搜索铺文章

GitHub&#xff1a;https://github.com/iccb1013/Sheng.WeixinConstruction因为个人精力时间有限&#xff0c;不会再对现有代码进行更新维护&#xff0c;不过微信接口比较稳定&#xff0c;经测试至今没有变化&#xff0c;功能依然全部可用&#xff0c;你可以在此基础上&#xf…...

怎么做阿里巴巴国际网站首页/广东今天新闻最新消息

2019独角兽企业重金招聘Python工程师标准>>> 今天在使用 codeigniter&#xff08;CI&#xff09;异步&#xff08;ajax&#xff09;传输数据时总是出现500 internal server error。 分两种分析&#xff0c;首先 如果使用url访问能够正确显示而没有这个错误&#xff…...

沈阳哪家网站制作公司比较好/关键词排名监控批量查询

JSON数据格式 JSON&#xff1a;javaScript Object Notation缩写&#xff0c;是一种轻量级的数据交换格式。 特点&#xff1a; 1.易于阅读和编写。 2.易于解析和生成。 3.是javaScript的子集&#xff1a;原生javaScript支持JSON 区别JsonjavaScript对象含义只是一种数据格式…...

别人帮做的网站怎么修改/品牌咨询

策略模式&#xff1a;定义了算法族&#xff0c;分别分装起来&#xff0c;让它们之间可以相互替换&#xff0c;此模式让算法的变化可以独立于使用算法的用户。 /** * Created by wqc on 2017/10/3. * 算法抽象类&#xff08;武器抽象类&#xff09; */public interface WeaponBe…...