Gcd: 求最大公因数的函数
原理:(a,b)=(b,a%b);
当 a%b 等于零时 b 为最大公因数;
裴蜀定理
Ax+by=c 有整数解的充要条件为 <=>gcd(a,b)|c;
=> 充分条件 <= 必要条件 <=> 充要条件
Exgcd 扩展欧几里得 (二元一次不定方程解)
用 gcd 递归, 当 b=0 是, 返 x=1,y=0;
然后用右边的反推啊,
中国剩余定理 (孙子定理)
形如:
解法
- miller_rabin
- int gg[8] = {
- 2,3,5,7,13,29,37,89
- };
- bool miller_rabin(int a,int n)
- {
- int d=n-1,r=0;
- while (d%2==0)
- d/=2,r++;
- int x = kuaisumi(a,d,n);
- if (x==1) return true;
- for (int i=0;i<r;i++)
- {
- if (x==n-1) return true;
- x=(long long)x*x%n;
- }
- return false;
- }
- bool is_prime(int n)
- {
- if (n<=1) return false;
- for (int a=0;a<8;a++)
- if (n==gg[a]) return true;
- for (int a=0;a<8;a++)
- if (!miller_rabin(gg[a],n)) return false;
- return true;
- }
积性函数
以上为积性函数 ^
莫比乌斯函数:
来源: http://www.bubuko.com/infodetail-3012453.html