選定方向了，這篇博客將伴隨我學習數論和某些數學知識

1.歐幾里得算法（輾轉相除法）

用途：求兩個數最大公約數

公式：a%b=b%(a%b)

代碼 ：? ? ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}? ?///函數形式

2.拓展歐幾里得

用途：求不定方程最小解（ 方程應滿足ax+by=gcd(a,b),否則無解?）

公式推導：（嫖的）

假設 ax1 + by1= gcd(a,b);

假設 bx2 + (a % b)y2= gcd(b,a % b);

根據樸素的歐幾里德原理有gcd(a,b) = gcd(b,a % b);

則:ax1 + by1 = bx2+ (a % b)y2;

即:ax1 + by1 = bx2 + (a - [a / b] * b)y2 = ay2 + bx2 - [a / b] * by2;

也就是ax1 + by1 == ay2+ b(x2 - [a / b] *y2);

根據恒等定理得：x1 = y2; y1 = x2 - [a / b] * y2;

這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2。

我們可以通過不斷遞歸調用求解。

代碼：

ll exgcd(ll a,ll b,ll &x,ll &y) {if(!b){x=1,y=0;return a;}ll ans=exgcd(b,a%b,x,y);ll t=x;x=y;y=t-a/b*y;return ans; }

x,y是一組解，返回的ans是gcd(a,b)

x，y的通解為

kx=b/ans

ky=-a/ans

*x=x+kx*n? ?*y=y+ky*n? ? (n為任意值）?

例題：青蛙的約會?

題目鏈接：http://poj.org/problem?id=1061

題干：

兩只青蛙在網上相識了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發現它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。可是它們出發之前忘記了一件很重要的事情，既沒有問清楚對方的特征，也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時間跳到同一點上，不然是永遠都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面。?
我們把這兩只青蛙分別叫做青蛙A和青蛙B，并且規定緯度線上東經0度處為原點，由東往西為正方向，單位長度1米，這樣我們就得到了一條首尾相接的數軸。設青蛙A的出發點坐標是x，青蛙B的出發點坐標是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費的時間相同。緯度線總長L米。現在要你求出它們跳了幾次以后才會碰面。?

題解：

設跳t次后，兩青蛙相遇，則滿足方程? ? ? (x+t*m)%L=(y+t*n)%L??

化簡下得? ? ? x-y=(n-m)*t+kL滿足ax+by=c的關系式? 如c整除gcd(a,b)則方程有解，注意這里的c是h*gcd(a,b),所以想直接調用函數還得等式兩邊同時乘? c/gcd(a,b)

代碼：

#include <iostream> using namespace std; typedef long long ll; ll exgcd(ll a,ll b,ll &x,ll &y) {if(!b){x=1,y=0;return a;}ll ans=exgcd(b,a%b,x,y);ll t=x;x=y;y=t-a/b*y;return ans; } int main() {ll x,y,m,n,l,p,c,a,b;cin>>x>>y>>m>>n>>l;a=n-m; c=x-y; b=l;if(a<0) { a=-a;c=-c; }p=exgcd(a,b,x,y);if(c%p!=0)cout<<"Impossible\n";else{x=x*c/p;ll t=b/p;if(x>=0) x=x%t;else x=x%t+t;cout<<x<<endl;}return 0; }

?

3.歐拉篩數

這里不介紹其他的篩質數方法了

原理：

對于任意一個合數，我們可以拆成最小質數*某個數字的形式。我們枚舉i，然后再從第一個質數開始枚舉，進行篩選。 為了保證每個合數只被最小質因數篩選，當我們枚舉的質數可以整除i時，如果再往大里枚舉，枚舉的質數就不可能是最小質數了

代碼：

int cntprime = 0; for (int i = 2; i <= n; i++) {if (!flag[i]) prime[++cntprime] = i;for (int j = 1; j <= cntprime && prime[j] * i <= n; j++){flag[i * prime[j]] = true;if (i % prime[j] == 0)break;} }

時間復雜度極其接近于O(n);

?

4.逆元及費馬小定理

在計算機運算過程中，分數是一個很難計算和保留精確度的東西，所以對于分數而言，我們一般會表示為mod某數的逆元

(a*x）%mod=1? x稱為a在mod下的逆元

費馬小定理就是? ?當加入p為質數且? ?a,p互質則? ? a^(p-1)=1(mod p)

即：在求某數的逆元的時候? ? ? 如果mod是質數的話? 則只需計算? ?a^(p-2)%p;

?

5.快速冪與矩陣快速冪

參考另一篇：https://blog.csdn.net/permi_yaxileni/article/details/98319067

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //看心情更，不過會一直更的

?

?

6.

總結

以上是生活随笔為你收集整理的超简单的数论入门题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。