文章目录
数论
组合数学
数学
费马大定理
费马大定理：当n>2时 a
n
+b
n
=c
n
,无解
-
当n==2 时 对于 a
2
+b
2
==c
2
;
来说满足
当n为奇数时 他们分别为 a, (a
2
)/2,)a
2
)/2+1; 例如 5,12,13； 3,4,5；
当n为偶数时 他们分别为a,(a
2
)/4-1,(a
2
)/4+1; 例如 4，3, 5；6 8 10；
贝祖定理:
- ax+by=m;判断是否有解：如果m是gcd(a,b)的若干倍。则这个式子一定有整数解。否则没有整数解。
欧几里得(gcd)
- （辗转相除）求法:
int gcd (int a,int b){
whhile(b){
int temp=a%b;
a=b;
b=temp;
}
return a;
}
- 或者用递归的想法
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
STEIN
stein算法的时间空间复杂度都和欧几里得相同,而且只需要位移和加减求可以实现，在常数方面更为优秀。
原理:
g
c
d
(
k
a
,
k
b
)
=
k
∗
g
c
d
(
a
,
b
)
g c d ( k a , k b ) = k ∗ g c d ( a , b )
g
c
d
(
k
a
,
k
b
)
=
k
∗
g
c
d
(
a
,
b
)
设x，y为非0奇数，有以下结论：
-
gc
d
(
x
,
0
)
=
x
g c d ( x , 0 ) = x
g
c
d
(
x
,
0
)
=
x
-
gc
d
(
2
x
,
2
y
)
=
2
g
c
d
(
x
,
y
)
g c d ( 2 x , 2 y ) = 2 g c d ( x , y )
g
c
d
(
2
x
,
2
y
)
=
2
g
c
d
(
x
,
y
)
-
gc
d
(
2
x
,
y
)
=
g
c
d
(
x
,
y
)
g c d ( 2 x , y ) = g c d ( x , y )
g
c
d
(
2
x
,
y
)
=
g
c
d
(
x
,
y
)
-
gc
d
(
x
,
y
)
=
g
c
d
(
∣
x
−
y
∣
,
m
i
n
(
x
,
y
)
)
g c d ( x , y ) = g c d ( ∣ x − y ∣ , m i n ( x , y ) )
g
c
d
(
x
,
y
)
=
g
c
d
(
∣
x
−
y
∣
,
m
i
n
(
x
,
y
)
)
很显然，第4个式子两个奇数相减会出来一个偶数，那么就可以继续往下除二了。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL stein(LL a, LL b) {
if(!a)
return b;
if(!b)
return a;
if(!(a & 1) && !(b & 1))
return stein(a >> 1, b >> 1) << 1;
else if(!(a & 1))
return stein(a >> 1, b);
else if(!(b & 1))
return stein(a, b >> 1);
return stein(abs(a - b), min(a, b));
}
int main() {
while(1) {
LL a, b;
cin >> a >> b;
cout << stein(a, b) << "\n";
}
}
扩展欧几里得
-
求ax+by=c的解，可以用贝祖定理来判断是否有解。
-
在有解的情况下求解，c=d*gcd(a,b),则方程式可化成
(a/d)*x+(b/d)*y=gcd(a,b)
;令m=a/d,n=b/d
即mx+ny=gcd(m,n);
求解之后应该得到的是m与n的值
要求解得x的值，所以x=dm,y=dn; -
有解的情况下，求最优解(最小正整数）。
ax+by=gcd(a,b);
==bx+(a-a/b
b)y=gcd(b,b%a)
==整理得 ay++b(x-a/b
y)=gcd(a,b);
即推出递推式-
x=y
y=y-a/b*x
;
-
-
简单的来说，就是一个不断回溯的过程，想让函数一直运行，直到a%b==0时 最后的得到这样一个方程 a*x=gcd(a,b);,即x=1，y0;时成立
然后一步步的回溯得到x 和y的特解. -
==最后返回的是gcd(a,b);这个不要弄错。
-
如果还是不懂就结合代码看就能帮助理解了，
-
代码：
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 temp=y; //把x y变成上一层的
y=x-(a/b)*y;
x=temp;
return r; //得到a b的最大公因数
}
- 再来一个求特解的代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include <bits/stdc++.h>
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 temp=y; //把x y变成上一层的
y=x-(a/b)*y;
x=temp;
return r; //得到a b的最大公因数
}
int main(){
int a,b,c,x,y;
cin>>a>>b>>c;
int m=exgcd(a,b,x,y);//c 表示gcd 而 x y分别是解
if(c%m==0)
cout<<m<<" "<<x*c/m<<" "<<y*c/m<<" "<<endl;
return 0;
}
- 这个是ax+by=c;输入的是a,b,c;求x，y,m是gcd(a,b)；
- 应该差不多了吧，嘻嘻qwq。
同余问题
-
ax=1%(n);也就是 ax%n==1%n;
ax=1+kn; k为倍数
所以只要满足 ax+bn=1的线性解 x,n都满足要求；
然后根据欧几里得算法，ax+bn=1 (a与b互质时 存在解) 或者 ax+bn=c ,c=t*gcd(a,b) 存在解。
逆元
说明一下 逆元不一定就是平时我们说的a 和 a
-1
这种；(这是狭义的)
这里说的是模系下的逆元，就是a*b%m=1；就说在m模系下a是b的逆元。
-
当a,m互质是，若ax=1(mod m),则称x是 a关于模m的逆元，即做z
-1
.在[0,m)的范围内，逆元是唯一的
费马小定理(a,m必须互质) 求逆元
-
逆元：a
m-1
=(1modm); -
推导过程： a
m-1
=a*a
m-2
=(1mod m); -
即a
m-2
就是a的逆元；
费马大定理
ｎ>2时 x
n
+y
n
=z
n
无解
当ｎ＝２时ａ
2
+b
2
=c
2
当ｎ是奇数时 解为：ａ (a
2
/2 )-1 (a
2
/2)+1;
当ｎ是偶数时 解为： a (a
2
/4)-1 (a
2
/4)+1;
扩展欧几里得求逆元
-
ax+my=gcd(a,m); 因为a,m互质 所以gcd(a,m)=1
即ax+my=1; 用同余定理得 ax(mod m)=(1mod m);
即x为a的逆元；
欧拉定理求逆元
- 说欧拉定理求逆元之前，先说一下欧拉函数
欧拉函数
欧拉定理
-
a
φ(m)
==1(mod m);
==a*a
φ(m)-1
==1(mod m);
也就是ax=1(mod m)的形式，所以a
φ(m)-1
是a的逆元。
中国剩余定理
大佬的博客.orz
https://www.cnblogs.com/MashiroSky/p/5918158.html
-
先看一道poj上的题目：
【poj1006】 Biorhythms
-
题意：
人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。 -
分析：
首先我们要知道，任意两个峰值之间一定相距整数倍的周期。假设一年的第N天达到峰值，则下次达到峰值的时间为N+Tk(T是周期，k是任意正整数)。所以，三个峰值同时出现的那一天(S)应满足
S=N1+T1∗k1=N2+T2∗k2=N3+T3∗k3
N1,N2,N3分别为为体力，情感，智力出现峰值的日期， T1，T2,T3分别为体力，情感，智力周期。 我们需要求出k1,k2,k3三个非负整数使上面的等式成立。
想直接求出k1,k2,k3貌似很难，但是我们的目的是求出S， 可以考虑从结果逆推。根据上面的等式，S满足三个要求：除以T1余数为N1，除以T2余数为N2，除以T3余数为N3。这样我们就把问题转化为求一个最小数，该数除以T1余N1，除以T2余N2，除以T3余N3。这就是著名的中国剩余定理，我们的老祖宗在几千年前已经对这个问题想出了一个精妙的解法。依据此解法的算法，时间复杂度可达到O(1)。
/****************************
分割线
*******************************************/
中国剩余定理
在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：
-
找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。
用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23。这个余数23就是符合条件的最小数。
就这么简单。我们在感叹神奇的同时不禁想知道古人是如何想到这个方法的，有什么基本的数学依据吗？ -
我们将“孙子问题”拆分成几个简单的小问题，从零开始，试图揣测古人是如何推导出这个解法的。
-
首先，我们假设n1是满足除以3余2的一个数，比如2，5，8等等，也就是满足3∗k+2（k>=0）的一个任意数。同样，我们假设n2是满足除以5余3的一个数，n3是满足除以7余2的一个数。
-
有了前面的假设，我们先从n1这个角度出发，已知n1满足除以3余2，能不能使得n1+n2的和仍然满足除以3余2？进而使得n1+n2+n3的和仍然满足除以3余2？
-
这就牵涉到一个最基本数学定理，如果有a%b=c，则有(a+k∗b)%b=c(k为非零整数)，换句话说，如果一个除法运算的余数为c，那么被除数与k倍的除数相加（或相减）的和（差）再与除数相除，余数不变。这个是很好证明的。
-
以此定理为依据，如果n2是3的倍数，n1+n2就依然满足除以3余2。同理，如果n3也是3的倍数，那么n1+n2+n3的和就满足除以3余2。这是从n1的角度考虑的，再从n2，n3的角度出发，我们可推导出以下三点：
为使n1+n2+n3的和满足除以3余2，n2和n3必须是3的倍数。
为使n1+n2+n3的和满足除以5余3，n1和n3必须是5的倍数。
为使n1+n2+n3的和满足除以7余2，n1和n2必须是7的倍数。 -
因此，为使n1+n2+n3的和作为“孙子问题”的一个最终解，需满足：
n1除以3余2，且是5和7的公倍数。
n2除以5余3，且是3和7的公倍数。
n3除以7余2，且是3和5的公倍数。 -
所以，孙子问题解法的本质是从5和7的公倍数中找一个除以3余2的数n1，从3和7的公倍数中找一个除以5余3的数n2，从3和5的公倍数中找一个除以7余2的数n3，再将三个数相加得到解。在求n1，n2，n3时又用了一个小技巧，以n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。也就是先求出5和7的公倍数模3下的逆元，再用逆元去乘余数。
-
这里又有一个数学公式，如果a%b=c，那么(a∗k)%b=a%b+a%b+…+a%b=c+c+…+c=k∗c(k>0),也就是说，如果一个除法的余数为c，那么被除数的k倍与除数相除的余数为k∗c。展开式中已证明。
-
最后，我们还要清楚一点，n1+n2+n3只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉掉3，5，7的公倍数105即可。道理就是前面讲过的定理“如果a%b=c，则有(a−k∗b)%b=c”。所以（n1+n2+n3）%105就是最终的最小解。
-
这样一来就得到了中国剩余定理的公式：
-
设正整数
两两互素，则同余方程组
-
有整数解。并且在模
下的解是唯一的， -
解为
-
其中
，而
为
模
的逆元。
/****************************
分割线
*******************************************/
中国剩余定理扩展——求解模数不互质情况下的线性方程组：
-
普通的中国剩余定理要求所有m
i
的互素，那么如果不互素呢，怎么求解同余方程组？ -
这种情况就采用两两合并的思想，假设要合并如下两个方程：
- 那么得到：
- 我们需要求出一个最小的x使它满足：
-
那么x1和x2就要尽可能的小，于是我们用扩展欧几里得算法求出x1的最小正整数解，将它代回a1+m1x1，得到x的一个特解x′，当然也是最小正整数解。
-
所以x的通解一定是x′加上lcm(m1,m2)∗k，这样才能保证x模m1和m2的余数是a1和a2。由此，我们把这个x′当做新的方程的余数，把lcm(m1,m2)当做新的方程的模数。（这一段是关键）
-
合并完成：
#include <map>//互质情况
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=2e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;
map<ll,ll>mp;
ll n,m,cnt,sum,a[maxn],b[maxn];
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
ll exgcd(ll a,ll b,ll &x,ll &y)//扩欧
{
if(b==0){
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y=y-a/b*x;
return d;
}
int main (){
n=read();
cnt=1;
for(int i=1;i<=n;i++)
{
a[i]=read();
b[i]=read();
cnt=a[i]*cnt;
}
for(int i=1;i<=n;i++)
{
ll ans=cnt/a[i];
ll x,y;
exgcd(ans,a[i],x,y);
x=(x%a[i]+a[i])%a[i];
sum=(sum+x*b[i]*ans)%cnt;
}
cout<<sum<<endl;
return 0;
}