拓展欧几里得
裴蜀定理
对于任意整数a,b，存在一对整数x,y，满足ax + by = gcd(a,b)
拓展欧几里得就是求出裴蜀定理解的算法
例题：
给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi使其满足 ai×xi+bi×yi=gcd(ai,bi)
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 ai,bi
输出格式
输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。
本题答案不唯一，输出任意满足条件的 xi,yi 均可。
数据范围
1≤n≤10^5^
1≤ai,bi≤2×10^9^输入样例：
2 4 6 8 18输出样例：
-1 1 -2 1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
Int x = new Int();
Int y = new Int();
exgcd(a, b, x, y);
System.out.println(x.v + " " + y.v);
}
sc.close();
}
private static int exgcd(int a, int b, Int x, Int y){
if (b == 0){
x.v = 1;y.v = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
y.v -= a / b * x.v;
return gcd;
}
}
class Int{
int v;
public Int() {
}
public Int(int v) {
this.v = v;
}
}线性同余方程
给定整数a，b，m，求一个整数x满足a * x ≡ b (mod m)，或者给出无解。因为未知数的指数为1，所以我们称之为一次同余方程，也称线性同余方程。
例题：
给定 n 组数据 ai,bi,mi对于每组数求出一个 xi，使其满足 ai×xi≡bi(modmi) 如果无解则输出
impossible。输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组数据 ai,bi,mi
输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出
impossible。每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。
数据范围
1≤n≤10^5^
1≤ai,bi,mi≤2×10^9^输入样例：
2 2 3 6 4 3 5输出样例：
impossible -3
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
int m = sc.nextInt();
Int x = new Int();
Int y = new Int();
int d = exgcd(a, m, x, y);
if (b % d == 1) System.out.println("impossible");
else System.out.println((long)b / d * x.v % m);
}
sc.close();
}
private static int exgcd(int a, int b, Int x, Int y){
if (b == 0){
x.v = 1;y.v = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
y.v -= a / b * x.v;
return gcd;
}
}
class Int{
int v;
public Int() {
}
public Int(int v) {
this.v = v;
}
}中国剩余定理
在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之 剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。
例题：
给出 n 个同余方程 x ≡ ri (mod pi)的 pi, ri，求出 x 的最小非负整数解。若无解则输出”-1”（没有引号）。
输入格式
第一行包含一个正整数 n(1 ≤ n ≤ 10^5^)，表示同余方程的个数。
接下来 n 行，每行两个正整数 pi,ri(1 ≤ pi ≤ 10^12^,0 ≤ ri＜p)。
数据保证所有 p 的最小公倍数不超过10^18^。
注意运算过程中的乘法溢出。
输出格式
输出同余方程的最小非负整数解，若无解输出”-1”（没有引号）。
输入样例：
2 8 7 11 9输出样例：
31
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static BigInteger a[] = new BigInteger[100005];
static BigInteger m[] = new BigInteger[100005];;
static int n;
static BigInteger x,y;
static BigInteger v0 = BigInteger.valueOf(0);
static BigInteger v1 = BigInteger.valueOf(1);
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
n = sc.nextInt();
for(int i = 1; i <= n; ++i) {
m[i] = sc.nextBigInteger();
a[i] = sc.nextBigInteger();
}
excrt();
}
}
private static BigInteger exgcd(BigInteger a,BigInteger b)
{
if(b.equals(v0)) {
x = v1;
y = v0;
return a;
}
BigInteger r = exgcd(b,a.remainder(b));
BigInteger z = x;
x = y;
y = z.subtract(a.divide(b).multiply(y));
return r;
}
private static void excrt() {
BigInteger M = m[1], A = a[1], t, d;
for(int i = 2; i <= n; ++i) {
d = exgcd(M, m[i]);
if(a[i].subtract(A).remainder(d).compareTo(v0) != 0) {
System.out.println("-1");
return;
}
x = x.multiply((a[i].subtract(A)).divide(d));
t = m[i].divide(d);
x = (x.remainder(t).add(t)).remainder(t);
A = M.multiply(x).add(A);
M = M.divide(d).multiply(m[i]);
A = A.remainder(M);
}
A = A.remainder(M).add(M).remainder(M);
System.out.println(A);
}
}容斥原理
例题：
给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。
输入格式
第一行包含整数 n 和 m。
第二行包含 m 个质数。
输出格式
输出一个整数，表示满足条件的整数的个数。
数据范围
1≤m≤16
1≤n,pi≤10^9输入样例：
10 2 2 3输出样例：
7
import java.util.Scanner;
public class Main {
static int N = 20;
static int q[] = new int[N];
static int n,m;
static long res;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < m; i++) {
q[i] = sc.nextInt();
}
for (int i = 1; i < 1 << m; i++) {
int t = 1,cnt = 0;
for (int j = 0; j < m; j++) {
if ((i >> j & 1) == 1){
if ((long)t * q[j] <= n){
t *= q[j];
cnt ++;
}
else {
t = -1;
break;
}
}
}
if (t != -1){
if (cnt % 2 == 1) res += n / t;
else res -= n / t;
}
}
System.out.println(res);
sc.close();
}
}