基础算法 位运算以及优化技巧 快读 1 2 3 4 5 6 7 8 9 std::ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); inline int read () { int x = 0 , f = 1 ; char ch = getchar (); while (ch < '0' || ch > '9' ) { if (ch == '-' ) f = -1 ; ch = getchar (); } while (ch >= '0' && ch <= '9' ) { x = (x << 1 ) + (x << 3 ) + (ch ^ 48 ); ch = getchar (); } return x * f; }
位运算 1 2 求n的第k位数字: n >> k & 1 返回n的最后一位1 :lowbit (n) = n & -n
一、高精度 1.高精度加法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <string> using namespace std;const int N = 510 ;int a[N], b[N], c[N];int main () { string str1; string str2; cin >> str1; cin >> str2; for (int i = 0 ; i < str1.size (); i ++) a[str1.size ()-1 - i] = str1[i] - '0' ; for (int i = 0 ; i < str2.size (); i ++) b[str2.size ()-1 - i] = str2[i] - '0' ; int len = max (str1.size (), str2.size ()); for (int i = 0 ; i < len; i ++){ c[i] += a[i] + b[i]; c[i+1 ] += c[i] / 10 ; c[i] %= 10 ; } len += 1 ; if (c[len-1 ] == 0 && len > 1 ) len -= 1 ; for (int i = 0 ; i < len; i ++) cout << c[len-1 -i]; return 0 ; }
2.高精度减法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <String> using namespace std;const int N=510 ;int a[N],b[N],c[N];int main () {string s1, s2; cin >> s1 >> s2; if (s1.size () < s2.size () || s1.size () == s2.size () && s1 < s2) { swap (s1, s2); cout << "-" ; } int len = max (s1.size (), s2.size ());for (int i = 0 ; i < s1.size (); ++i) { a[s1.size () - 1 - i] = s1[i] - '0' ; } for (int i = 0 ; i < s2.size (); ++i) { b[s2.size () - 1 - i] = s2[i] - '0' ; } for (int i = 0 ; i < len; ++i) { if (a[i] < b[i]) { a[i + 1 ]--; a[i] += 10 ; } c[i] = a[i] - b[i]; } while (c[len - 1 ] == 0 && len > 1 ) { len--; } for (int i = len - 1 ; i >= 0 ; --i) { cout << c[i]; } return 0 ; }
3.高精度乘低精度 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <iostream> #include <string> using namespace std;const int N=510 ;int a[N],b,c[N];int main () { string s; cin>>s>>b; int len=s.size (); for (int i=0 ;i<len;i++) { a[len-1 -i]=s[i]-'0' ; } for (int i=0 ;i<len;i++) { c[i]+=a[i]*b; c[i+1 ]+=c[i]/10 ; c[i]%=10 ; } while (c[len]>0 ) { c[len+1 ]+=c[len]/10 ; c[len]%=10 ; len++; } while (c[len-1 ]==0 &&len>1 ) { len--; } for (int i=len-1 ;i>=0 ;i--) { cout<<c[i]; } return 0 ; }
4.高精度乘高精度 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <iostream> #include <string> using namespace std;const int N=510 ;int a[N],b[N],c[N];int main () { string s1,s2; cin>>s1>>s2; for (int i=0 ;i<s1.size ();i++) { a[s1.size ()-1 -i]=s1[i]-'0' ; } for (int i=0 ;i<s2.size ();i++) { b[s2.size ()-1 -i]=s2[i]-'0' ; } for (int i=0 ;i<s1.size ();i++) { for (int j=0 ;j<s2.size ();j++) { int k=i+j; c[k]+=a[i]*b[j]; c[k+1 ]+=c[k]/10 ; c[k]%=10 ; } } int len=s1.size ()+s2.size ()+1 ; if (c[len-1 ]>0 )len++; while (c[len-1 ]==0 &&len>1 ) { len--; } for (int i=len-1 ;i>=0 ;i--) { cout<<c[i]; } return 0 ; }
5.低精度除法高精商 a除以b,要求输出小数点后n位
1 2 3 4 5 6 7 8 9 10 11 12 13 int a, b, n, c[100 ];c[0 ] = a / b; int t = a % b;for (int i = 1 ; i <= n; ++i) { c[i] = t * 10 / b; t = t * 10 - c[i] * b; } cout << c[0 ] << '.' ; for (int i = 1 ; i <= n; ++i) { cout << c[i]; }
6.高精度除法低精度商 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 string s1, s2; int b, t, x;cin >> s1 >> b; for (int i = 0 ; i < s1.size (); ++i) { a[i] = s1[i] - '0' ; } t = x = 0 ; for (int i = 0 ; i < s1.size (); ++i) { c[i] = (t * 10 + a[i]) / b; t = (t * 10 + a[i]) % b; } while (c[x] == 0 && x < s1.size ()) { x++; } for (int i = x; i < s1.size (); ++i) { s2 += c[i] + '0' ; } cout << s2 << ' ' << t;
二、分数计算 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 #include <iostream> #include <cmath> using namespace std;int gcd (int a,int b) { if (b==0 )return a; return gcd (b,a%b); } struct Frac { int up; int down; }; Frac reduction (Frac result) { if (result.down<0 ) { result.up=-result.up; result.down=-result.down; } if (result.up==0 ) { result.down=1 ; } else { int d=gcd (abs (result.up),abs (result.down)); result.up/=d; result.down/=d; } return result; } Frac multi (Frac f1,Frac f2) { Frac result; result.up=f1.up*f2.up; result.down=f1.down*f2.down; return reduction (result); } Frac divide (Frac f1,Frac f2) { Frac result; result.up=f1.up*f2.down; result.down=f1.down*f2.up; return reduction (result); } Frac add (Frac f1,Frac f2) { Frac result; result.up=f1.up*f2.down+f1.down*f2.up; result.down=f1.down*f2.down; return reduction (result); } Frac minu (Frac f1,Frac f2) { Frac result; result.up=f1.up*f2.down-f1.down*f2.up; result.down=f1.down*f2.down; return reduction (result); } void show (Frac r) { r=reduction (r); if (r.down==1 )printf ("%lld\n" ,r.up); else if (abs (r.up)>r.down) { printf ("%d %d/%d\n" ,r.up/r.down,abs (r.up)%r.down,r.down); } else printf ("%d/%d\n" ,r.up,r.down); } int main () { int a,b,c,d; cin>>a>>b>>c>>d; Frac f,e,r; f.up=a;e.up=c; f.down=b;e.down=d; show (f); show (e); r=add (f,e); show (r); r=minu (f,e); show (r); r=multi (f,e); show (r); r=divide (f,e); show (r); return 0 ; }
三、前缀和 1.一维前缀和
dp[i]表示从下标1开始到下标i的一维数组元素之和,若计算区间[a,b]的数组元素之和,其中递推式sum=dp[j]-dp[i-1].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> using namespace std;const int N=100010 ;int arr[N],dp[N];int main () { int n; cin>>n; for (int i=1 ;i<=n;i++) { cin>>arr[i]; } for (int i=1 ;i<=n;i++) { dp[i]=dp[i-1 ]+arr[i]; } return 0 ; }
2.二维前缀和
s(i,j)表示从(1,1)开始到(i,j)位置的二维数组所有元素之和,其中递推式为s(i,j)+=s(i-1,j)+s(i,j-1)-s(i-1,j-1),则从(a+1,b+1)到(c,d)的和为s[a,b]+s[c,d]-s[a,d]-s[b,c].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <iostream> #include <string> using namespace std;int n,l,r,t,arr[605 ][605 ],count,sum[605 ][605 ];bool judge (int x,int y) { double sumval=0 ;int num=0 ; int left=max (1 ,x-r),right=min (n,x+r); int down=max (1 ,y-r),up=min (n,y+r); sumval = sum[right][up] - sum[right][down-1 ] - sum[left-1 ][up] + sum[left-1 ][down-1 ]; num=(right-left+1 )*(up-down+1 ); double ave=sumval*1.00 /num; if (ave<=t)return true ; return false ; } int main () { ios::sync_with_stdio (false ); cin>>n>>l>>r>>t; for (int i=1 ;i<=n;i++) { for (int j=1 ;j<=n;j++) { cin>>arr[i][j]; sum[i][j]=arr[i][j]; sum[i][j] += sum[i - 1 ][j] + sum[i][j - 1 ] - sum[i - 1 ][j - 1 ] ; } } for (int i=1 ;i<=n;i++) { for (int j=1 ;j<=n;j++) { if (judge (i,j))count++; } } cout<<count<<endl; return 0 ; }
四、差分 差分是求前缀和的逆操作,对于原数组a[n],构造出一个b[n]数组中,使a[n]为b[n]的前缀和。一般用于快速对整个数组进行操作,比如将a数组中[l,r]部分的数据全部加上c.使用暴力的方法,则时间复杂度至少为O(n),而使用差分算法时间复杂度降低到O(1).
1.一维差分 创建一数组b,使得数组a为数组b的前缀和,数组b为数组a的差分
构造方法:b[i] = a[i] - a[i - 1]
此处使用了一个虚拟的构造方式(在数组一个位置加上一个数,那么在它的下一个位置减去这一数)
应用:对于a数组的任意区间[l, r],令其加上一个数,而不改变其它值
b[l] += c, b[r + 1] -= c
差分操作和前缀和一样数组下标都从1开始。
b[l]+c后,l后面的数组都会加c。r后面的数据也会被改变,要改回来就得b[r+1]-c.
模板题如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 输入一个长度为 n 的整数序列。接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r] 之间的每个数加上 c。 请你输出进行完所有操作后的序列。输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数,表示整数序列。 接下来 m 行,每行包含三个整数 l,r,c,表示一个操作。输出格式 共一行,包含 n 个整数,表示最终序列。数据范围 1 ≤n,m≤100000 ,1 ≤l≤r≤n,−1000 ≤c≤1000 , −1000 ≤整数序列中元素的值≤1000 输入样例: 6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1 输出样例: 3 4 5 3 4 2 #include <iostream> using namespace std;const int N = 1e6 +10 ;int a[N],b[N];int main () { int n,m; cin>>n>>m; for (int i = 1 ; i <= n; i ++ )cin>>a[i]; for (int j = 1 ; j <= n; j ++ ) { b[j]=a[j]-a[j-1 ]; } while (m -- ) { int l,r,c; cin>>l>>r>>c; b[l]=b[l]+c; b[r+1 ]=b[r+1 ]-c; } int sum=0 ; for (int i = 1 ; i <= n; i ++ ) { sum=sum+b[i]; cout<<sum<<" " ; } return 0 ; }
2.二维差分 直接得出公式b[i][j] += c, b[i + 1][j] -= c, b[i][j + 1] -= c, b[i + 1][j + 1] += c
每次对b数组执行以上操作,等价于:
1 2 3 for (int i=x1;i<=x2;i++) for (int j=y1;j<=y2;j++) a[i][j]+=c;
模板题如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。输入格式 第一行包含整数 n,m,q。 接下来 n 行,每行包含 m 个整数,表示整数矩阵。 接下来 q 行,每行包含 5 个整数 x1,y1,x2,y2,c,表示一个操作。 输出格式 共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。数据范围 1 ≤n,m≤1000 ,1 ≤q≤100000 ,1 ≤x1≤x2≤n,1 ≤y1≤y2≤m,−1000 ≤c≤1000 , −1000 ≤矩阵内元素的值≤1000 输入样例: 3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1 输出样例: 2 3 4 1 4 3 4 1 2 2 2 2 #include <iostream> #include <cstdio> using namespace std;const int N = 1e3 + 10 ;int a[N][N], b[N][N];void insert (int x1, int y1, int x2, int y2, int c) { b[x1][y1] += c; b[x2 + 1 ][y1] -= c; b[x1][y2 + 1 ] -= c; b[x2 + 1 ][y2 + 1 ] += c; } int main () { int n, m, q; cin >> n >> m >> q; for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= m; j++) cin >> a[i][j]; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { insert (i, j, i, j, a[i][j]); } } while (q--) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; insert (x1, y1, x2, y2, c); } for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { b[i][j] += b[i - 1 ][j] + b[i][j - 1 ] - b[i - 1 ][j - 1 ]; } } for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { cout<<b[i][j]; } cout<<endl; } return 0 ; }
五、二分 整数二分 对lower_bound来说,它寻找的就是第一个满足条件“值大于等于x”的元素的位置;对
upper_bound函数来说,它寻找的是第一个满足“值大于 x”的元素的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 bool check (int x) {} int bsearch_1 (int l, int r) {while (l < r){ int mid = l + r >> 1 ;if (check (mid)) r = mid; else l = mid + 1 ;} return l;} int bsearch_2 (int l, int r) {while (l < r){ int mid = l + r + 1 >> 1 ;if (check (mid)) l = mid;else r = mid - 1 ;} return l;}
浮点数二分 1 2 3 4 5 6 7 8 9 10 11 12 bool check (double x) {} double bsearch_3 (double l, double r) {const double eps = 1e-6 ; while (r - l > eps){ double mid = (l + r) / 2 ;if (check (mid)) r = mid;else l = mid;} return l;}
六、排序 快速排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void quick_sort (int q[], int l, int r) {if (l >= r) return ;int i = l - 1 , j = r + 1 , x = q[l + r >> 1 ];while (i < j){ do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap (q[i], q[j]);} quick_sort (q, l, j), quick_sort (q, j + 1 , r);}
边界问题
因为边界问题只有这两种组合,不能随意搭配
1 2 3 4 5 x不能取q[l]和q[l+r>>1 ]; quick_sort (q,l,i-1 ),quick_sort (q,i,r);x不能取q[r]和q[(l+r+1 )>>1 ]; quick_sort (q,l,j),quick_sort (q,j+1 ,r);
归并排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void merge_sort (int q[], int l, int r) {if (l >= r) return ;int mid = l + r >> 1 ;merge_sort (q, l, mid);merge_sort (q, mid + 1 , r);int k = 0 , i = l, j = mid + 1 ;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0 ; i <= r; i ++, j ++ ) q[i] = tmp[j];}
七、数学问题 快速幂 1 2 3 4 5 6 7 8 9 10 11 12 typedef long long llll binaryPow (ll a,ll b) { ll ans=1 ; while (b) { if (b&1 )ans*=a; b>>=1 ; a*=a; } return ans; }
素数筛法 1.朴素筛法 1 2 3 4 5 6 7 8 9 10 bool isprime (int n) { if (n<=1 )return false ; for (int i=2 ;i<=sqrt (n);i++) { if (n%i==0 )return false ; } return true ; }
2.埃氏(Eratosthenes)筛法 假设要筛2-n内的素数,则先将2的倍数从里面剔除,再将3的倍数从里面剔除,以此类推……时间复杂度为O(nloglogn),已经非常接近线性了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> using namespace std;const int maxn=101 ;int prime[maxn],pnum=0 ;bool p[maxn];void find_prime () { for (int i=2 ;i<maxn;i++) { if (p[i]==false ) { prime[pnum++]=i; for (int j=i;j<maxn;j+=i) { p[j]=true ; } } } } int main () { find_prime (); for (int i=0 ;i<pnum;i++) { cout<<prime[i]<<" " ; } return 0 ; }
3.欧拉(Euler)筛法 欧拉筛法是埃氏筛法的改进,埃氏筛法终究会出现一个数被多个数筛掉的情况。例如因为120 = 2^3 x 3 x 5,因为2,3,5是120的质因子,所以120会被2筛一次,被3筛一次,被5筛一次,共3次。
而欧拉筛法保证了每一个合数都被其最小质因子筛去,保证不会重复筛除。故遍历一次就好,时间复杂度为O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream> using namespace std;const int N=100 ;bool p[N];int prime[N],pnum=0 ;void find_prime () { for (int i=2 ;i<=N;i++) { if (p[i]==false ) { prime[pnum++]=i; } for (int j=0 ;j<pnum&&i*prime[j]<=N;j++) { p[i*prime[j]]=true ; if (i%prime[j]==0 )break ; } } } int main () { find_prime (); for (int i=0 ;i<pnum;i++) { cout<<prime[i]<<" " ; } return 0 ; }
4、试除法分解质因子 1 2 3 4 5 6 7 8 9 10 11 12 void divide (int x) {for (int i = 2 ; i <= x / i; i ++ )if (x % i == 0 ){ int s = 0 ;while (x % i == 0 ) x /= i, s ++ ;cout << i << ' ' << s << endl; } if (x > 1 ) cout << x << ' ' << 1 << endl;cout << endl; }
组合数求解 公式: $$ C_n^m=1(m=0或m=n)\ c_n^m=c_{n-1}^m+c_{n-1}^{m-1}(n>m>0) $$
所以,我们可以使用动态规划来求解组合数,直接上代码。
1 2 3 4 5 6 7 8 9 for (int i = 0 ; i <= n; ++i) { dp[i][i] = dp[i][0 ] = 1 ; } for (int i = 0 ; i <= n; ++i) { for (int j = 1 ; j < i; ++j) { dp[i][j] = dp[i - 1 ][j] + dp[i - 1 ][j - 1 ]; } }
观察到每一行的组合数都只需要用到上一行组合数的数值,所以可以进行状态压缩 ,注意倒序处理。
1 2 3 4 5 6 for (int i = 0 ; i <= n; ++i) { for (int j = i; j >= 0 ; --j) { if (j == i || j == 0 ) dp[j] = 1 ; else dp[j] = dp[j] + dp[j - 1 ]; } }
进制转换 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <iostream> #include <map> using namespace std;map<char ,int >mp1; map<int ,char >mp2; int num,temp;char ans[1000 ];int main () { for (int i=0 ;i<10 ;i++) { mp1[i+'0' ]=i; mp2[i]=i+'0' ; } for (char i='A' ;i<='F' ;i++) { mp1[i]=i-'A' +10 ; mp2[i-'A' +10 ]=i; } int d; cin>>d; string str; cin>>str; for (int i=0 ;i<str.size ();i++) { temp=temp*d+mp1[str[i]]; } int a; cin>>a; while (temp) { ans[num++]=mp2[temp%a]; temp/=a; } for (int i=num-1 ;i>=0 ;i--) { cout<<ans[i]; } return 0 ; }
最大公约数与最小公倍数 辗转相除法(欧几里得算法)最大公约数
时间复杂度为O(logb)
定理
当a与b都为正整数且a>b时,记gcd(a,b)为a与b的最大公约数,则有gcd(a,b)=gcd(b, a mod b)
证明
a可以表示成 a = kb + r(a,b,k,r皆为正整数,且r不为0)
假设d是a,b的一个公约数,则有d|a,d|b,即a和b都可以被d整除。(x|y意为kx = y,k为正整数)
而r = a - kb,两边同时除以d,r/d = a/d - kb/d,由等式右边可知m = r/d为整数,因此d|r
因此d也是b,a mod b的公约数
故(a,b)与(b, a mod b)的公约数相等,则其最大公约数也相等,得证。
举例
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法,是这样进行的: 1997 / 615 = 3 (余 152) 615 / 152 = 4(余7) 152 / 7 = 21(余5) 7 / 5 = 1 (余2) 5 / 2 = 2 (余1) 2 / 1 = 2 (余0) 至此,最大公约数为1。
1.递归版 1 2 3 4 5 int gcd (int a,int b) { if (b==0 )return a; else return gcd (b,a%b); }
2.循环版 1 2 3 4 5 6 7 8 9 10 11 12 int gcd (int a,int b) { int c; while (a % b != 0 ) { c = a % b; a = b; b = c; } return b; }
3.内置函数 C++可以使用内置函数__gcd(a,b)来求两数的最大公约数,使用时需包含头文件algorithm。
4.求最大公倍数 1 2 3 4 int lcm (int a,int b) { return a/gcd (a,b)*b; }
扩展欧几里得算法 给定两个整数a和b,求一组整数解(x,y)使得ax+by=gcd(a,b)成立,其中gcd(a,b)表示a和b的最大公约数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int exgcd (int a,int b,int &x,int &y) { if (b==0 ) { x=1 ; y=0 ; return a; } int g=exgcd (b,a%b,x,y); int temp=x; x=y; y=temp-a/b*y; return g; }
求欧拉函数 1 2 3 4 5 6 7 8 9 10 11 12 int phi (int x) {int res = x;for (int i = 2 ; i <= x / i; i ++ )if (x % i == 0 ){ res = res / i * (i - 1 ); while (x % i == 0 ) x /= i;} if (x > 1 ) res = res / x * (x - 1 );return res;}