一 : 定理
费马小定理 扩展欧几里德 乘法逆元 https://www.cnblogs.com/xcfxcf/p/12304658.html
欧拉定理
中国剩余定理
一个正整数K,给出K Mod 一些质数的结果,求符合条件的最小的K。例如,K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。
第1行:1个数N表示后面输入的质数及模的数量。(2 <= N <= 10) 第2 - N + 1行,每行2个数P和M,中间用空格分隔,P是质数,M是K % P的结果。(2 <= P <= 100, 0 <= K < P)
输出
输出符合条件的最小的K。数据中所有K均小于10^9。
输入样例
3
2 1
3 2
5 3
输出样例
23
![同余](https://www.ccppcoding.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
#include <bits/stdc++.h> using namespace std; #define int long long int n,p[15],m[20]; 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 -= x * (a / b); return d; } int China(int n,int *m,int *a){//剩余定理 int M = 1,d,y,x = 0; for(int i = 0; i < n; i++) M *= m[i]; for(int i = 0; i < n; i++){ int w = M / m[i]; exgcd(m[i],w,d,y); x = (x + y * w * a[i]) % M; } return (x + M) % M; } signed main(){ ios::sync_with_stdio(0); cin >> n; for(int i = 0; i < n; i++) cin >> p[i] >> m[i]; cout << China(n,p,m); return 0; }
View Code
二:同余方程
求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。
输入格式
输入只有一行,包含两个正整数a,b,用一个空格隔开。
输出格式
输出只有一行,包含一个正整数x,表示最小正整数解。
输入数据保证一定有解。
数据范围
2≤a,b≤2∗1e9,2≤a,b≤2∗1e9
输入样例:
3 10
输出样例:
7
![同余](https://www.ccppcoding.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 int a,b,x,y; 5 int exgcd(int a,int b,int &x,int &y){ 6 if(!b){ 7 y = 0, x = 1; 8 return a; 9 } 10 int d = exgcd(b,a % b,y,x); 11 y -= x * (a / b); 12 return d; 13 } 14 signed main(){ 15 //freopen("in","r",stdin); 16 ios::sync_with_stdio(0); 17 cin >> a >> b; 18 exgcd(a,b,x,y); 19 cout << (x % b + b) % b; 20 return 0; 21 }
View Code
kmo,
原文链接: https://www.cnblogs.com/hazelxcf/p/12318196.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
![同余](https://www.ccppcoding.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/329904
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!