算法都是套路系列-数论模板

🌸数论基本模板

🍂闰年

public class Text { public static void main(String[] args) { } static boolean isloop(int x) { return x%400==0 || (x%4==0 && x%100!=0); } }

🍂求某年某月某日是星期几

public static int whatDay(int year, int month, int day){ if(m <= 2){ y--; m += 12; } return (day + 2 * month + 3 * (month - 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1; }

🍂求当年到当前天具体有多少天

public static int calDays(int year, int month, int day){ int sum = 0; int[] month = {0, 31,28,31,30,31,30,31,31,30,31,30,31}; if(isLeap(year)){ month[2]++; } for(int i= 1; i < m; i++){ sum += month[i]; } return sum + day; }

🍂求距离公元一年一月一日的天数

public static int days(int y, int m, int d){ int c = calDays(y, m, d); return 365 * (y - 1) + (y - 1) / 4 - (y - 1) / 100 + (y - 1) / 400 + c; }

🍂素数

static boolean isPrim(int n) { if(n==1) return false; for(int i=2;i*i<=Math.sqrt(n);i++) if(n%i==0) return false; return true; } //倍筛法 boolean[] is = new boolean[1000005]; is[1] = true;//true表示不是素数 for(int i=2;i<1000005;i++) if(!is[2]) for(int j=2*i;j<1000005;j+=i) is[j] = true; System.out.println(is[2004]);

🍂gcd和lcm

public class Text { public static void main(String[] args) { } static int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } static int lcm(int a,int b) { return a*b/gcd(a,b); } }

🍂扩展欧几里得

static int x, y; public static int exgcd(int a, int b) { if(b == 0) { x = 1; y = 0; return a; } int d = exgcd(b, a % b); int t = y; y = x - a / b * y; x = t; return d; }

🍂n阶行列式

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Text { static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); public static int Int(String s) { return Integer.parseInt(s); } public static void copy(int[][] A, int[][] A1, int i, int len) { for(int x = 1; x < len; x++) { for(int y = 0, j = 0; j < len; j++) { if(j != i) { A1[x - 1][y++] = A[x][j]; } } } } public static int F(int[][] A, int len) { int res = 0; if(len == 1) { return A[0][0]; } if(len == 2) { return A[0][0] * A[1][1] - A[0][1] * A[1][0];//递归出口 }else { int A1[][] = new int[10][10]; for(int i = 0; i < len; i++) { copy(A, A1, i, len);//得到余子式 res += Math.pow(-1, i) * A[0][i] * F(A1, len - 1);//递归式 } } return res; } public static void main(String[] args) throws NumberFormatException, IOException { int n; n = Integer.parseInt(in.readLine()); int arr[][] = new int[10][10]; for(int i = 0; i < n; i++) { String[] s = in.readLine().split(" "); for(int j = 0; j < n; j++) { arr[i][j] = Int(s[j]); } } out.write(F(arr, n) + "\n"); out.flush(); } }

🍂进制问题

如有价值1，2，4，8等价值的硬币，如何用最小的硬币数凑出100元

static int f(int n,int k) {//调用API转成k进制，缺点题目有上界为8 int ans=0; String s = Integer.toString(n, k); System.out.println(s); for(int i=0;i<s.length();i++) ans+=s.charAt(i)-'0'; return ans; }

🍂找钱问题

共1024，64，16，4，1几种面值

static void solve(){ Scanner cin = new Scanner(System.in); int N = 1024-cin.nextInt(), ans = 0; for(int i=0; i<4; i++){ ans += N/arr[i]; N %= arr[i]; } System.out.println(ans); }

🍂括号匹配

public boolean isValid(String s) { if(s==null||s.equals("")) return true; char[] ch = s.toCharArray(); Stack<Character> stack = new Stack<>(); for(int i=0;i<ch.length;i++) { if(ch[i]=='(' || ch[i]=='[' || ch[i]=='{') stack.push(ch[i]); else if(ch[i]==')' || ch[i]==']' || ch[i]=='}') { if(!stack.isEmpty()) { char p = stack.pop(); if(p=='(' && ch[i]==')') continue; if(p=='[' && ch[i]==']') continue; if(p=='{' && ch[i]=='}') continue; } return false; } } return stack.empty(); }

🍂快速幂

求a^n

public class Text { private static long MOD = 1000000007; public static void main(String[] args) { } public static long mpow(long a, long n) {// if(n == 0 || a == 1) { return 1; } long ans = 1; while(n != 0) { if(n % 2 == 1) { ans = a * ans % MOD; } a = a * a % MOD; n >>= 1; } return ans; } }

🍂矩阵乘法

public class Text { private static int MOD = 100000007; public static void main(String[] args) { } static int[][] mul(int[][] a, int[][] b) { int n = a.length; int[][] ans = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % MOD;// ans[i][j] += a[i][k]*a[k][j]; return ans; } }

🍂矩阵快速幂

public class Text { public static void main(String[] args) { } private static int MOD = 100000007; static int[][] mul(int[][] a, int[][] b) { int n = a.length; int[][] ans = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % MOD;// ans[i][j] += a[i][k]*a[k][j]; return ans; } public static int[][] mpow(int[][] a, int n){ int N = a.length; int[][] ans = new int[N][N]; for(int i = 0; i < N; i++) { ans[i][i] = 1;//初始化为单位矩阵 } while(n > 0) {//写 n!=0也行,，反正位运算是会更快 if((n & 1) == 1) { ans = mul(ans, a); } a = mul(a, a); n >>= 1; } return ans; } }

🍂欧拉函数

小于n的正整数中与n互质的数的数目（φ(1)=1）

public class Text { public static void main(String[] args) { } /** * 欧拉函数 : 小于n的正整数中与n互质的数的数目（φ(1)=1） * F(n) = n * (1 - 1 / p1)*(1 - 1/ p2) * (1 - 1/p3) * ...*(1 - 1/ pn) * @param n * @return */ public static int euler(int n) { int ans = n; for(int i = 2; i <= n; i++) { if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) { n /= i; } } } return ans; } public static int euler2(int n) { int ans = n; for(int i = 2; i * i <= n; i++) { if(n % i == 0) { ans = ans / i * (i - 1); //n * (1 - 1/p)转化为n / p(p - 1) while(n % i == 0) { n /= i; } } } if(n > 1) { //优化 O(sqrt(n)) 不过要在出口 if(n>1)ans/n*(n-1) O(n)不用 ans = ans / n * (n - 1); } return ans; } }

🍂前缀和模板

import java.util.Scanner; public class Text { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int[] sum = new int[n + 1]; for(int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + input.nextInt();//前i个数的和 } input.close(); } }

🍂求组合数C(n, m)

其实求解组合数有很多方法

例如

C(n, m) = n! / m!(n - m)! C(n, m) = A(n, m) / A(m, m) C(n, m) = C(n, n - m) import java.util.Scanner; public class Text { public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); f = new long[n + 5]; inv = new long[n + 5]; f[0] = 1; for (int i = 1; i < n + 5; i++) { f[i] = f[i - 1] * i % mod; inv[i] = mpow(f[i], mod - 2); } in.close(); } static int n; static long mod = 1000000009; static long[] f; static long[] inv; static long C(int n, int m) { return f[n] * inv[m] % mod * inv[n - m] % mod; } static long mpow(long a, long n) {// 快速幂 if (n == 0 || a == 1) return 1; long ans = 1; while (n != 0) { if (n % 2 == 1) ans = a * ans % mod; a = a * a % mod; n >>= 1; } return ans; } }

🍂乘法逆元(费小马定理)

public static long qmi(long a, long b, long p){ // 快速幂求逆元 long res = 1; while(b != 0){ if((b&1) == 1){ res = res * a % p; } b >>= 1; a = a * a % p; } return res; } public static void Init(){ infact[0] = 1; // 存储逆元 fact[0] = 1; for(int i = 1; i <= 100000; i++){ fact[i] = fact[i-1] * i % mod; infact[i] = infact[i-1] * qmi(i, mod - 2, mod) % mod; } }

🍂大数加法

public class Main{ static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] agrs) throws IOException{ String s = in.readLine(); String s1 = in.readLine(); int lena = s.length(); int lenb = s1.length(); // 也可以用静态数组。 ArrayList<Integer> a = new ArrayList<>(); ArrayList<Integer> b = new ArrayList<>(); for(int i = lena - 1; i >= 0; i--) a.add(s.charAt(i) - '0'); // 先对数字进行处理，保存在数组中。 for(int i = lenb - 1; i >= 0; i--) b.add(s1.charAt(i) - '0');// 因为需要从个位开始加，所以倒序存储。 ArrayList<Integer> c = new ArrayList<>(); // c = a + b int r = 0; for(int i = 0; i < lena || i < lenb; i++){ if(i < lena) r += a.get(i); if(i < lenb) r += b.get(i); c.add(r%10); r /= 10; } // 最后判断一下最高位是否进位。 if(r != 0) c.add(r); for(int i = c.size()-1; i >= 0; i--) out.write(c.get(i) + ""); // 倒序输出。因为write函数的特性，要将结果转化为字符串输出。 out.flush(); } }

🍂大数乘法

public class Main{ static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); static int[] a = new int[1000], b = new int[1000], c = new int[1000]; public static void main(String[] args) throws IOException{ String s = in.readLine(); String s1 = in.readLine(); int lena = s.length(); int lenb = s1.length(); for(int i = lena - 1, j = 0; i >= 0; i--, j++) a[j] = s.charAt(i) - '0'; for(int i = lenb - 1, j = 0; i >= 0; i--, j++) b[j] = s1.charAt(i) - '0'; for(int i = 0; i < lena; i++) for(int j = 0; j < lenb; j++){ c[i+j] += a[i] * b[j]; c[i+j+1] += c[i+j]/10; // 进位。 c[i+j] %= 10; // 保留的值 } int lenc = lena + lenb - 1; // 两数乘积的最大位数为 lena + lenb, 数组下标从0开始，所以最大是lena + lenb - 1 while(c[lenc] == 0 && lenc > 0) lenc --; // 移除前导0 for(int i = lenc; i >= 0; i--){ out.write(c[i] + ""); } out.flush(); } }