俯视膜拜初等数论

本文主要是介绍俯视膜拜初等数论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一部分：质数

质数

---

又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
质数是一个孤独的数字呀！

质因数分解

---

什么是质因数分解？

就是将一个数字分解成几个质数相乘。小学时候我们就学过的，很简单。比如$9=3*3$；但是 $64=8*8$ 就不对了，因为8不是质数啊！

有什么用？

用处很大很大的！后面的求欧拉函数就是在这个的基础之上建立的。

思路是什么？

我暂时也不能理解为什么这么干。

代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;vector<int> factor(int n)
{vector<int> ans;for (int i = 2; i <= sqrt(n); i++){while (n%i == 0){ans.push_back(i);n /= i;}}if (n > 1){ans.push_back(n);}return ans;
}int main()
{int n;cin >> n;vector<int>ans=factor(n);for (int i = 0; i < ans.size(); i++){cout << ans[i] << " ";}
}

欧拉函数

欧拉函数是什么?

在数论，对正整数$n$，欧拉函数是小于$n$的正整数中与$n$互质的数的数目$φ(1)=1$。此函数以其首名研究者欧拉命名(Euler’so totient function)。 例如$φ(8)=4$，因为$1,3,5,7均和8$互质。
这里有一个求欧拉函数的简便方法

思路

基于上面的分解质因数的算法

代码

XX

第二部分：求解不定方程

欧几里得算法

---

扩展欧几里得算法

---

怎么证明是对的？

忘了

有什么用？

可以用来求 $ax+by=gcd(a,b)$中的$x和y$的值。

那么问题来了如何求$ax+by=z$的值呢？只需要将 $ax+by=gcd(a,b)$的解$x1和y1$扩大$z/gcd(a,b)$倍就可以了。

举个例子：
我可以直接先求$3x+7y=(3, 7)$的解，也就是$3x+7y=1$的解。我们得到$x=-2，y=1$。然后我们将$x和y$扩大$50/(3, 7)$倍，也就是$50/1$倍，得到$x=-2*50, y=1*50$。于是我们得到了$3x+7y=50$的解是$-100和50$。

代码

#include <iostream>
using namespace std;
int gcdEx(int a, int b, int &x, int &y) 
{if(b==0){x=1;y=0;return a;}int r = gcdEx(b, a%b, x, y);int x1 = x, y1 = y;x = y1;y = x1 - (a / b) * y1;return r;
}
int main()
{int x, y;cout<<gcdEx(47, 30, x, y)<<"\n";cout<<x<<" "<<y;return 0;
}

解二元一次不定方程

---

有什么卵用？

可以求逆元啊！！
同余方程可以转为不定方程，所以解同余方程可以看成解不定方程。

代码

#include <iostream>
using namespace std;
int gcdEx(int a, int b, int &x, int &y)
{if (b == 0){x = 1;y = 0;return a;}int r = gcdEx(b, a%b, x, y);int x1 = x, y1 = y;x = y1;y = x1 - (a / b) * y1;return r;
}
int main()
{int x, y;int a, b, c; //ax+by=ccin >> a >> b>> c;int numGcd = gcdEx(a, b, x, y);cout << c / numGcd * x << " " << c / numGcd * y;return 0;
}

逆元

---

逆元是什么？逆天啊！

当a，m互质，若$ax\equiv1(mod m)$，则x是a关于模m的逆元。

逆元有什么用？

我也不知道

怎么求逆元

当a，m互质，$ax\equiv1(mod m)$。我们知道$ax\equiv1(mod m)$ 等价于$ax+my=1$。那么$ax+my=1$不就是个不定方程吗？直接用exgcd解不就行了吗？
注意解出的x可能是负数，如果是负数我们就直接加上m就行了。依据是不定方程通解公式，如下。

思路

就把它当做一个不定方程的问题来处理就行了。

代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;int exgcd(int a, int b, int &x, int &y)
{if (b == 0){x = 1;y = 0;return a;}int r = exgcd(b, a%b, x, y);int x1 = x;int y1 = y;x = y1;y = x1 - (a / b) * y1;return r;
}// 求逆元
int inverse(int a, int m)
{int x, y;exgcd(a, m, x, y);return x;
}int main()
{int a, m;cin >> a >> m;int ans = inverse(a, m);if (ans < 0){cout << ans + m;}else{cout << ans;}
}

这篇关于俯视膜拜初等数论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---