数论快速入门（同余、扩展欧几里德、中国剩余定理、大素数测定和整数分解、素数三种筛法、欧拉函数以及各种模板）
数学渣渣愉快的玩了一把数论，来总结一下几种常用的算法入门，不过鶸也是刚刚入门，
所以也只是粗略的记录下原理，贴下模板，以及入门题目（感受下模板怎么用的）
（PS:文中亮色字体都可以点进去查看百度原文）
附赠数论入门训练专题：点我打开专题（题目顺序基本正常，用以配套数论入门）
一、同余定理
同余式 ： a ≡ b (mod m) (即 a%m == b%m)简单粗暴的说就是：若 a-b == m 那么 a%m == b%m
这个模运算性质一眼看出。。。直接上入门水题：
Reduced ID Numbers
附AC代码（这个也没啥模板。。。。知道就好）
#include
#include
#include
#include
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
/*
同余：
ifa-b == m
thena%m == b%m*/
const int N = 1000000;
bool vis[N+5];
int a[N+5];
bool ol[N+5];
int main()
{int T;cin>>T;while (T--){int n;scanf("%d",&n);mem(vis,0);for (int i = 1;i <= n;++i) scanf("%d",a+i);for (int i = 1;i <= n;++i){for (int j = i+1;j <= n;++j){int d = abs(a[i]-a[j]);vis[d] = 1;}}bool fd = 0;for (int m = 1;!fd;++m){if (!vis[m]){mem(ol,0);bool ok = 1;for (int i = 1;ok&&i <= n;++i){if (ol[a[i]%m]) ok = 0;else ol[a[i]%m] = 1;}if (ok){printf("%d\n",m);fd = 1;}}}}return 0;
}
二、扩展欧几里德算法
这个扩展是从原欧几里德算法扩展而来，这个算法真心非常有用！非常有用！非常有用！（中国剩余定理也要用到它）
首先说欧几里德算法(其实就是我们小时候数学课上就学过的辗转相除法求gcd)
欧几里德说：gcd(a,b) = gcd(b,a%b)
于是得到欧几里德算法：
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}PS:__gcd(a,b)库函数可以直接调用，但是有些OJ上提交会CE
现在，我们令a,b的最大公因数为gcd,那么我们一定可以找到一组x,y满足：（这个是欧几里德的定理一）
a*x + b*y = gcd;此时，我们设x0,y0是上述不定方程的特解，那么就可以用x0,y0表示出整个不定方程的通解
x = x0 + (b/gcd)*t;
y = y0 - (a/gcd)*t;然后是怎么求解通解x,y?
倒过去看看欧几里德算法，显然，它的结束条件是 b = 0的时候返回a
这就意味着，终止状态是 ：a = gcd ,b = 0;
将这组a,b代会不定方程ax+by=gcd,可以得到一组特解：x = 1,y = 0
找到终止状态，我们再看看递归的过程：
gcd = b*x1 + (a%b)*y1 = b*x1 + (a-(a/b)*b)*y1 // a%b = a-(a/b)*b= b*x1 + a*y1 - (a/b)*b*y1= a*y1 + b*(x1-a/b*y1)最后得到gcd = a*y1 + b*(x1-a/b*y1)和原来的式子gcd = a*x + b*y一对比就得到:
x = y1,y = x1 - a/b*y1;上面两个等式很重要！！（因为模板里面会直接用到，如果是直接背模板就得把它背熟）
下面就是扩展欧几里德算法：
int e_gcd(int a,int b,int &x,int &y)
{if (b == 0){x = 1,y = 0;return a;}int ans = e_gcd(b,a%b,x,y);int tmp = x;x = y;y = tmp - a/b*y;
}这个算法本质上还是求a,b的最大公因数，只是在计算的过程中顺带计算x,y(同时体验了一把引用的神奇)
扩展欧几里德算法有什么用？反正用法很多，它可以求解形如 ax+by=c的通解
但是实际应用中通常指要求在通解中选一些特殊的解，
比如一个数对于另一个数的乘法逆元。那么什么是乘法逆元？
ax ≡ 1(mod b) // ax % b = 1ax%b = 1,可以化成 ax = by + 1
显然，它等价于这样的表达式：ax + by = 1
这个式子很眼熟有木有！！！如果等式右边是gcd(a,b)就好了！！！
然后这里copy欧几里德的三个定理：
定理一:如果d = gcd(a,b),则必能找到正的或负的整数x和y使d = ax + by
定理二:若gcd(a,b) = 1,则方程ax≡c(mod b)在[0,b-1]上有唯一解
定理三:若gcd(a,b) = d,则方程ax≡c(mod b)在[0,b|d01]上有唯一解于是，对上述方程 ax + by = 1, 当gcd(a,b) != 1的时候无解
故方程ax + by = c 有解的条件是 ： c%gcd(a,b) = 0;
按乘法逆元讲，一般，我们能找到无数组解满足条件，但一般题目是求解最小的那组解
假设我们求出了特解x0,那么 ，只需要用x0 % b就是最小解了
为什么？（这个我没管，反正知道是这个。。。。后面贴的参考资料链接里面有。。。）
另外，有的时候求得的特解可能是个负数，或者说b是负数，怎么办？
如果b是负数，取b的绝对值
如果x0是负数，让x0对|b|取模后再加上|b|
然后，直接上模板代码：
int Cal(int a,int b)//求最小的x使ax+ by = 1
{int x,y;int gcd = e_gcd(a,b,x,y);if (1%gcd) return -1;//无解x*=1/gcd;b = abs(b);int ans = x%b;if (ans <= 0) ans += b;return ans;
}下面给出求最小逆元的代码：
typedef long long ll;
ll e_gcd (ll a, ll b, ll& x, ll& y)
{if (b == 0){x = 1, y = 0;return a;}ll ans = e_gcd (b, a % b, y, x);y -= a / b * x; //这个和前面用的方法不一样，不过是对的，写起来更快、return ans;
}
ll Cal(ll a,ll b,ll c)//求最小的x使ax+ by = c
{ll x,y;ll gcd = e_gcd(a,b,x,y);if (c%gcd) return -1;//无解x*=c/gcd;b /= gcd;if (b < 0) b = -b;ll ans = x%b;if (ans <= 0) ans += b;return ans;
}来一道入门级的裸的扩展欧几里德的题感受下模板怎么用：
PS:方程还是要自己列，然后用扩展欧几里德求解
青蛙的约会
AC代码供参考：
#include
#include
#include
#include
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
ll e_gcd(ll a,ll b,ll &x,ll &y)
{if (b == 0){x = 1,y = 0;return a;}ll ans = e_gcd(b,a%b,x,y);ll tmp = x;x = y;y = tmp - a/b*y;return ans;
}
ll cal(ll a,ll b,ll c)//求最小的x使ax+by=c
{ll x,y;ll gcd = e_gcd(a,b,x,y);if (c%gcd != 0) return -1;x *= c/gcd;b/=gcd;if (b < 0) b = -b;ll ans = x%b;if (ans <= 0) ans += b;return ans;
}
int main()
{ll xa,xb,va,vb,L;while (~scanf("%lld %lld %lld %lld %lld",&xa,&xb,&va,&vb,&L)){ll ans = cal(vb-va,L,xa-xb);if (ans == -1) puts("Impossible");else printf("%lld\n",ans);}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！