GDPU 竞赛技能实践天码行空9

1. 埃式筛法

求区间[2, n]内所有的素数对

💖 Main.java

import java.util.Scanner;public class Main
{static int N = (int) 1e8, cnt = 0;static int[] p = new int[N];static boolean[] st = new boolean[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();getPrimes(n);print();}private static void print(){for (int i = 0; i < cnt; i++)System.out.print(p[i] + " ");}private static void getPrimes(int n){for (int i = 2; i <= n && i < N; i++){if (!st[i]){p[cnt++] = i;for (int j = 2; j * i <= n; j++)st[i * j] = true;}}}}

在这里插入图片描述

2. 求第1亿个Fibonacci数

👨‍🏫 参考地址

💖 Main.java

public class Main
{static long n, p;//	龟速乘法（快速积）static long qmul(long a, long b){long res = 0;while (b != 0){if ((b & 1) == 1){res = (res + a) % p;}a = (a + a) % p;b >>= 1;}return res;}//	矩阵乘法static void mul(long[][] a, long[][] b){
//		临时矩阵暂存结果long[][] tmp = new long[2][2];for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)for (int k = 0; k < 2; k++)tmp[i][j] = (tmp[i][j] + qmul(a[i][k], b[k][j])) % p;//		拷贝for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)a[i][j] = tmp[i][j];}//	计算斐波那契数列的第 n 项static long F(long n){
//		极端情况if (n == 0)return 0;//		根据fn来进行构造矩阵// fn，分别为f(1) f(2)long[][] f = { { 1, 1 }, { 0, 0 } };// 累乘矩阵long[][] a = { { 0, 1 }, { 1, 1 } };//      快速幂for (long k = n - 1; k != 0; k >>= 1){if ((k & 1) == 1)mul(f, a);mul(a, a);}return f[0][0];}public static void main(String[] args){n = (int) 1e8;// 10^8 == 1 亿p = Integer.MAX_VALUE; // 由于会爆int long 需要取模System.out.println("前20项：");for (int i = 0; i < 20; i++)System.out.print(F(i) + " ");System.out.println();System.out.println("第1亿项：" + F(n));}
}

在这里插入图片描述

3.Catalan数

即卡特兰数又称卡塔兰数，是组合数学中一个常出现在各种计数问题中的数列，以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。现请你写一段程序来计算Catalan数。
输入样例:

输出样例:

💖 Main.java

import java.util.Scanner;public class 卡特兰数
{static long cal(int n){long son = 1;long mum = 1;for (int i = 2 * n; i > n; i--)son *= i;for (int i = n; i >= 1; i--)mum *= i;return son / (mum * (n + 1));}public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();System.out.println(cal(n));}
}

在这里插入图片描述

4. 摆球

现将大小和形状相同的4个黑色球和4个红色球排成一排，从左边第一个球开始数，不管数几个不球，黑球数不少于红球数的排法有多少种？请编程实现。
卡特兰数的应用

💖 Main.java

public class Main
{static int N = 8;static long ans = 0;static long ans1 = 0;public static void main(String[] args){dfs(0, 0, 0);System.out.println(ans + " " + cal(4));}//	卡特兰数static long cal(int n){long son = 1;long mum = 1;for (int i = 2 * n; i > n; i--)son *= i;for (int i = n; i >= 1; i--)mum *= i;return son / (mum * (n + 1));}//	暴力枚举private static void dfs(int cur, int black, int red){if (cur >= 8){if (red == 4 && black == 4)ans++;return;}if (black > red)dfs(cur + 1, black, red + 1);dfs(cur + 1, black + 1, red);}}