算法学习14：数论（质数，约数，欧拉函数，快速幂）

2024-03-31 14:36
文章标签 算法 函数 学习 快速 质数 14 欧拉 数论 约数

本文主要是介绍算法学习14：数论（质数，约数，欧拉函数，快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法学习14：数论（质数，约数，欧拉函数，快速幂）

文章目录

  • 算法学习14：数论（质数，约数，欧拉函数，快速幂）
  • 前言
  • 要记忆的模版：
  • 一、质数
    • 1.质数的判定：试除法
    • 2.质因数的分解：试除法
    • 3.筛质数：埃氏筛、线性筛
  • 二、约数
    • 1.试除法求约数
    • 2.求约数个数、约数之和（懵懵的）
    • 3.辗转相处法求最大公约数（欧几里得定理）
    • 4.扩展欧几里得定理：
      • 线性同余方程：（和扩展欧几里得定理一样，不太理解，待以后解决）
  • 三、欧拉函数：1~n中，与n互质的数的个数叫做欧拉函数
    • 1.例题1：求一个数n的欧拉函数phi（n）
    • 2.例题2：给定一个正整数n，求1~n中每个数的欧拉函数之和
  • 四、快速幂
    • 1.例题：给定a，k，p，求出a^k mod p 的值
    • 2.给定a，p，其中p是质数，求a%p的乘法逆元，不存在则输出impossible
    • 在这里插入图片描述
  • 总结

前言

数论这个不分涉及到很多**“数学推导”**的部分，自我感觉这部分很难去理解，一些点很乱，须要后面遇到实际问题的时候去优化。

须要达成的目标：了解一些简单的数论知识，有个印象。比如：筛，欧几里得定理，快速幂。

在这里插入图片描述

要记忆的模版：

// 试除法求约数：
bool is_prime(int n)
{if(n < 2) return false;for(int i = 2; i <= n / i; i ++)if(n % i == 0) return false;return true; } // 分解质因数：
void divide(int n)
{for(int i = 2; i <= n / i; i ++)if(n % i == 0){while(n % i == 0) 	n /= i;printf("%d", i);}if(n > 1) printf("%d", n);					} // 例子：2310 = 2 * 3 * 5 * 7 * 11 
// 24 = 2 * 2 * 2 * 3

提示：以下是本篇文章正文内容：

一、质数

1.质数的判定：试除法

bool is_prime(int n)
{if(n < 2) return false;for(int i = 2; i <= n / i; i ++)if(n % i == 0) return false;return true; }

2.质因数的分解：试除法

c++求解质因数，了解什么是质因数

void divide(int n)
{for(int i = 2; i <= n / i; i ++)if(n % i == 0){while(n % i == 0) 	n /= i;printf("%d", i);}if(n > 1) printf("%d", n);					} // 例子：2310 = 2 * 3 * 5 * 7 * 11 
// 24 = 2 * 2 * 2 * 3void divide(int n)
{int i = 2;do {while(n % i==0) {cout << i;n /= i;if(n != 1) cout<<"*";}i++;}while(n!=1);
}// 筛质数：
// 埃氏筛 （对朴素筛的优化） void get_prime(int n)
{for(int i = 2; i <= n; i ++){if(!st[i]) {primes[cnt ++] = i;// 标记质数的倍数 for(int j = i; j <= n; j += i) st[j] = true;}} } // 线性筛 void get_prime(int n)
{for(int i = 2; i <= n; i ++){if(!st[i]) primes[cnt ++] = i;for(in j = 0; primes[j] <= n / j; j ++){st[primes[j] * i] = true;if(i % primes[j] == 0) break; }}}

3.筛质数：埃氏筛、线性筛

在这里插入图片描述

// 例题：给定一个n，求出1~n中质数的个数。
int primes[N], cnt;
bool st[N];// false：质数， true：合数 // primes：存储的是质数，cnt：质数的个数 // 朴素筛法 void get_prime(int n)
{for(int i = 2; i <= n; i ++){if(!st[i]) primes[cnt ++] = i;// 标记倍数 for(int j = i; j <= n; j += i) st[j] = true;} } // 埃氏筛 （对朴素筛的优化） void get_prime(int n)
{for(int i = 2; i <= n; i ++){if(!st[i]) {primes[cnt ++] = i;// 标记质数的倍数 for(int j = i; j <= n; j += i) st[j] = true;}} } // 线性筛 void get_prime(int n)
{for(int i = 2; i <= n; i ++){if(!st[i]) primes[cnt ++] = i;for(in j = 0; primes[j] <= n / j; j ++){st[primes[j] * i] = true;if(i % primes[j] == 0) break; }}}

二、约数

1.试除法求约数

// 给定一个n，求出n的所有约数
vector<int> get_divisors(int n)
{for(int i = 1; i <= n / i; i ++)// 遍历 if(n % i == 0){res.push_back(i);// 防止i*i == n ，就是n是i的平方 if(i != n / i) res.push_back(n / i);}sort(res.begin(), res.end());return res;
}

2.求约数个数、约数之和（懵懵的）

在这里插入图片描述

在这里插入图片描述

// 给定n个整数，请求出这些数约数的个数，
// 请求出这些数的乘积的约数之和。
// 思考：求一个和求一堆是一样的问题
typedef long long LL;unorder_map<int, int> primes;
while(n --)
{int x;cin >> x;for(int i = 2; i <= x / i; i ++)while(x % i == 0){x /= i;primes[i] ++;// 哈希表的：key：i，value：++ }
}
LL res = 1;// res为约数的个数 
for(auto prime : primes) 
res = res * (prime.second + 1) % mod;LL res = 1;// res为约数之和 
for(auto prime : primes)
{int p = prime.first, a = prime.second;LL t = 1;while(a --) t = (t * p + 1) % mod;res = res * t % mod;// 遍历完 }

3.辗转相处法求最大公约数（欧几里得定理）

求a和b的最大公约数

#include <iostream>using namespace std;int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}int main()
{int n;scanf("%d", &n);while(n --){int a, b;scanf("%d%d", &a, &b);printf("%d\n", gcd(a, b));}return 0;
}

在这里插入图片描述

4.扩展欧几里得定理：

在这里插入图片描述

// 给定n对正整数a，b，对于每对数，求出一组x，y，使其满足ax = gcd（a，b）；
// 还没理解清楚 
#include <iostream>using namespace std;// 传递x，y的引用。 
int exgcd(int a, int b, int &x, int &y)
{if(!b){x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;// d??? 
}int main()
{int n;scanf("%d", &n);while(n --){int a, b, x, y;scanf("%d%d", &a, &b);exgcd(a, b, x, y);printf("%d %d", x, y);}return 0;
}

线性同余方程：（和扩展欧几里得定理一样，不太理解，待以后解决）

给定n组数据a，b，m，对于每一组数据，取出一个x，使其满足ax = b（%m）

在这里插入图片描述

在这里插入图片描述

三、欧拉函数：1~n中，与n互质的数的个数叫做欧拉函数

在这里插入图片描述

1.例题1：求一个数n的欧拉函数phi（n）

// 求一个数n的欧拉函数phi（n）
#include <iostream>
#include <algorithm>using namespace std;int main()
{int n;cin >> n;while(n --){int a;cin >> a;int res = a;for(int i = 2; i <= a / i; i ++){if(a % i == 0){// res = res * (1 - 1 / a);res = res / a * (a - 1);// 对除号的变形 while(a % i == 0) a /= i;}}if(a > 1) res = res / a * (a - 1);cout << res << endl; } return 0;
}

在这里插入图片描述

2.例题2：给定一个正整数n，求1~n中每个数的欧拉函数之和

// 给定一个正整数n，求1~n中每个数的欧拉函数之和
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1e6 + 10;int primes[N], cnt;
int phi[N];
bool st[N];LL get_eulers(int n)
{phi[1] = 1;for(int i = 2; i <= n; i ++){if(!st[i]){primes[cnt ++] = i;phi[i] = i - 1;// 注意1.}for(int j = 0; primes[j] <= n / i; j ++){st[primes[j] * i] = true;if(i % primes[j] == 0) {phi[primes[j] * i] = phi[i] * primes[j];// 注意2 break;}phi[primes[j] * i] = phi[i] * (primes[j] - 1);// 注意3 }}LL res = 0;for(int i = 1; i <= n; i ++) res += phi[i];// 注意4 return res; 
}int main()
{int n;cin >> n;cout << get_eulers(n) << endl;	return 0;
}

在这里插入图片描述

四、快速幂

1.例题：给定a，k，p，求出a^k mod p 的值

在这里插入图片描述

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;// a^k mod p
int qmi(int a, int k, int p)
{int res = 1;while(k){// k的二进制末位为1 if(k & 1) res = (LL) res * a % p;k >>= 1;a = (LL) a * a % p;// a的平方 }return res;
}int main()
{int n;scanf("%d", &n);while(n --){int a, k, p;scanf("%d%d%d", &a, &k, &p);printf("%d", qmi(a, k, p));}return 0;}

在这里插入图片描述

2.给定a，p，其中p是质数，求a%p的乘法逆元，不存在则输出impossible

在这里插入图片描述

在这里插入图片描述

总结

提示：这里对文章进行总结：
💕💕💕

这篇关于算法学习14：数论（质数，约数，欧拉函数，快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/864567。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2