基础数学问题整理

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long 
#define MOD 1000000007
 
int cmp(int x, int y) {
	return x < y;
}
 
int a[100];
int main()
{
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a+i);
	}
	sort(a + 1, a + n + 1, cmp); // 升序排序
	 首先需要计算出所有的组合数
	ll ans = 1;
	for (int i = 1; i <= n; i++) {
		if (a[i] < i) {
			printf("0\n");
			return 0;
		}
		ans = ans * (a[i]-i+1) % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

​

#include<stdio.h>
#include<algorithm>
using namespace std;
int tran[2024][2024];//记录杨辉三角
int f[2024][2024];//状态转移 //f[n][m]=f[n-1][m-1]+f[n-1][m]
int t,m,n,k;
int main()
{
	scanf("%d%d", &t,&k);
	int maxi = 2010;
	for (int i = 0; i < maxi; i++)
		tran[i][0] = 1;
	int j;
	for (int i = 1; i <= maxi; i++) {
		int sum_tmp = 0;//当前行的和
		for (j = 1; j <= i; j++) {
			//printf("(%d,%d)%d+%d,", i,j,tran[i - 1][j - 1], tran[i - 1][j]);
			tran[i][j] = (tran[i - 1][j - 1] + tran[i - 1][j])%k;// 因为后面反正也是要看是不是k的倍数的
			//printf("%d,", tran[i][j]);
			if (tran[i][j] == 0) {
				sum_tmp++;
			}
			f[i][j] = f[i - 1][j] + sum_tmp; // 计算数量
			//printf("(i=%d,j=%d)%d ",i,j, f[i][j]);
		}
		f[i][j] = f[i][j - 1];//这是为了下面一行的转移
		//printf("\n");
	}
	for (int epoch = 1; epoch <= t; epoch++) {
		scanf("%d%d", &n, &m);
		m = min(m, n);
		//printf("n=%d m=%d\n", n, m);
		printf("%d\n", f[n][m]);
	}
	return 0;
}

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x%y); // 一句话搞定   这个相当于要是x>y那么就换个位置
}
 
bool check(int x, int y) {
	if (gcd(x, y) == 1)return 1;
	return 0;
}
 
int main()
{
	int t, a0, a1, b0, b1;
	scanf("%d", &t);
	int cnt;
	while (t--) {
		scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
		// 开始枚举
		cnt = 0;
		int mul_k = b1 / a1;
		//printf("mul_k=%d\n", mul_k);
		//printf("%d\n", int(sqrt(mul_k)));
		int x;
		// a1是公约数,b1是公倍数
		for (int now = 1; now<= sqrt(mul_k); now++) { // x=k1*a1=b1/k2 这里枚举的是k1(防止迭代变量变化,这里使用now作为迭代变量)
			int k = now;
			if (mul_k%k)continue;
			// 判断k时的情况
			x = k * a1; // 算出x
			if (x%a1 == 0 && b1 % x == 0) { // 满足倍数和约数
				if (check(a0 / a1, k) && check(b1 / b0, mul_k / k)) {
					cnt++;
				}
			}
			if (k*k == mul_k) continue;//重复的不用再算一次
			// 判断mul_k/k时的情况
			k = mul_k / k;
			x = k * a1; // 算出x
			if (x%a1==0 || b1 % x==0) { // 满足倍数和约数
				if (check(a0 / a1, k) && check(b1 / b0, mul_k / k)) {
					cnt++;
				}
			}
		}
		printf("%d\n", cnt);
	}
	return 0;
}

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define N 30000
using namespace std;
struct PipeNode {
	int num;
	int idx; // 当前质因数idx有num个
}pipeNode[N+20];
struct Flags {
	int num; 
	int x0; // 标记当前所属的初值(也就是每种细菌),每次分解质因数都要标记是属于哪种的,如果不匹配就是前面的,那么桶就不需要重复初始化
}flag[N+20]; // 下标就是质因数的数值
int n,m1,m2; // 细菌总数
int a[N+20];
int primes[N+1],prime_cnt;
int pipeCnt;// 试管质因数数量
bool check_prime(int x) {
	if (x % 2 == 0)return 0;
	for (int i = 3; i <= sqrt(x); i++) {
		if (x%i == 0)return 0;
	}
	return 1;
}
 
int main()
{
	scanf("%d", &n);
	scanf("%d%d", &m1, &m2);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	// 质因数打表
	primes[++prime_cnt] = 2;
	for (int i = 3; i <= N + 10; i++) {
		if (check_prime(i))primes[++prime_cnt] = i;
	}
	// 首先给试管做质因数分解
	if (m1 == 1) {
		printf("0\n");//一个就是初始数量,肯定可以满足
		return 0;
	}
	else {
		for (int i = 1; i <= prime_cnt; i++) {// 枚举质因数
			if (m1%primes[i] == 0) { // 如果可以分解
				pipeNode[++pipeCnt].idx = primes[i];
				pipeNode[pipeCnt].num = 0;
				while (m1%primes[i] == 0) {
					pipeNode[pipeCnt].num++;
					m1 /= primes[i];
				}
			}
			if (m1 == 1)break;//分解结束
		}
	}
	for (int i = 1; i <= pipeCnt; i++)pipeNode[i].num *= m2;// 质因数*倍数
	// 开始检查每种细菌
	int ans = 0x3f3f3f3f;//存储需要再过的最短时间
	for (int index = 1; index <= n; index++) {
		int x0 = a[index];
		//printf("a[index]=%d\n", a[index]);
		// 分解x0并装进桶里
		int x0_copy = x0;
		for (int i = 1; i <= prime_cnt; i++) {
			if (x0_copy%primes[i] == 0) {
				flag[primes[i]].x0 = x0;
				flag[primes[i]].num = 0;
				while (x0_copy%primes[i] == 0) {
					flag[primes[i]].num++;
					x0_copy /= primes[i];
				}
			}
			if (x0_copy == 1)break;
		}
		// 检查当前细菌是否可以达到菌均分
		int res = -1; // 找最大值,存在不符合要求的就是-1
		for (int i = 1; i <= pipeCnt; i++){ // 检查所有菌
			int num = pipeNode[i].num;
			int idx = pipeNode[i].idx;
			if (flag[idx].x0 != x0) {//x0当前没有质因数分解到idx(试管的某个质因数)
				res = -1;
				break;
			}
			int flag_num = flag[idx].num; // 菌初始值
			// 计算需要多长时间
			int det = max(0,num - flag_num);
			if (det) {
				res = max(res,(det - 1) / flag_num + 1);
			}
			else {
				res = max(res,0);
			}
			if (res > ans)break;//没必要算了
		}
		if (res != -1) {
			ans = min(ans, res);
		}
		if (ans == 0)break;//不用算了
	}
	if (ans == 0x3f3f3f3f) {
		printf("-1\n");
	}
	else {
		printf("%d\n", ans+1); // 初始时间为1
	}
	return 0;
}

#include<stdio.h>
int main()
{
	int a=0,n,x;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		a ^= x;// 取异或
	}
	printf("%d\n", a);
	return 0;
}

#include<stdio.h>
int a,b;
int res[100000], cnt; 
int main()
{
	scanf("%d%d", &a, &b);
	int a_copy = a;
	while (a != 1 && a != 0) {
		int div = a / b;
		int mod = a % b;
		//printf("div=%d mod=%d\n", div, mod);
		if (mod < 0) {
			mod -= b;
			div++;
		}
		res[++cnt] = mod;
		a = div;
	}
	if(a) res[++cnt] = a; // 最后一位是1保存下来,0就不要了
	printf("%d=", a_copy);
	for (int i = cnt; i >=1; i--) {
		if(res[i]<=9)
			printf("%d", res[i]);
		else printf("%c", 'A' + res[i] - 10);
	}
	printf("(base%d)", b);
	return 0;
}

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 1000000
int n;
int flag[N + 10];
int main()
{
	scanf("%d", &n);
	int x;
	int maxx = -1;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		maxx = max(x, maxx);
		// 分解所有质因数,存入flag
		for (int j = 1; j < sqrt(x); j++) {
			if (x%j == 0) {
				flag[j]++;
				flag[x / j]++;
			}
		}
		int sqrt_x = sqrt(x); // 特判
		if (pow(sqrt_x,2) == x) {
			flag[sqrt_x]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		while (flag[maxx] < i)maxx--;
		printf("%d\n", maxx); // 打印当前位置
	}
	return 0;
}