专栏文章

题解：P1591 阶乘数码

ssongliunuo
P1591题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miotnc92
此快照首次捕获于
2025/12/03 00:57
3 个月前
此快照最后确认于
2025/12/03 00:57
3 个月前
查看原文
水体讲解。

总体思路

重载运算符， 因为此题范围特别巨大, n!n! 大约是 1024910^{249} , 这个数据没有任何变量能一次性存下， 在进行阶乘运算， 最后便利如果等于 a 那么 cnt 自增。

题目写法

结构体

CPP
struct Bigint
  1. 结构体定义
CPP
int a[100005], len;
Bigint(int x = 0) {
	memset(a, 0, sizeof a);
	for (len = 1; x > 0; len++) {
		a[len] = x % 10;
		x /= 10;
	}
  len--;
}
  1. 重载"[]"
CPP
int &operator[](int i) {
	return a[i];
}
  1. 自定义进位函数
CPP
void flatten(int L) {
	len = L;
	for (int i = 1; i <= len; i++) {
		a[i + 1] += a[i] / 10;
		a[i] %= 10;
	}
	while (!a[len])len--;//去前导零
}
  1. 自定义输出函数
CPP
void print() {
	for (int i = max(1, len); i >= 1; i--) {
		cout << a[i];
	}
}

重载

CPP
Bigint operator
  1. 重载"+"
CPP
Bigint operator+ (Bigint a, Bigint b) {
	Bigint c;
	int len = max(a.len, b.len);
	for (int i = 1; i <= len; i++) {
		c[i] = a[i] + b[i];
	}
	c.flatten(len + 10);
	return c;
}
  1. 重载"*"
CPP
Bigint operator*(Bigint a, int b) {
	Bigint c;
	int len = a.len;
	for (int i = 1; i <= len; i++) {
		c[i] = a[i] * b;
	}
	c.flatten(len + 40);
	return c;
}

主函数

CPP
inr main()
  1. 定义及输入
CPP
int n, a, cnt = 0, t;
cin >> t;
  1. 循环输入
CPP
for (int i = 1; i <= t; i++) {
	cnt = 0;
	cin >> n >> a;
  1. 计算阶乘
CPP
Bigint ans(1);
for (int j = 1; j <= n; j++) {
	ans = ans * j;
}
  1. 计算答案
CPP
int len = ans.len;
for (int j = 1; j <= len; j++) {
	if (ans[j] == a)cnt++;
}
  1. 输出
CPP
  cout << cnt << "\n";
}

总体

CPP
#include<bits/stdc++.h>
using namespace std;
struct Bigint {//结构体
	int a[100005], len;
	Bigint(int x = 0) {
		memset(a, 0, sizeof a);
		for (len = 1; x > 0; len++) {
			a[len] = x % 10;
			x /= 10;
		}
		len--;
	}
	int &operator[](int i) {//定义符号"[]"
		return a[i];
	}
	void flatten(int L) {//定义进位
		len = L;
		for (int i = 1; i <= len; i++) {
			a[i + 1] += a[i] / 10;
			a[i] %= 10;
		}
		while (!a[len])len--;
	}
	void print() {
		for (int i = max(1, len); i >= 1; i--) {
			cout << a[i];
		}
	}
};
Bigint operator+ (Bigint a, Bigint b) {//重载运算符+
	Bigint c;
	int len = max(a.len, b.len);
	for (int i = 1; i <= len; i++) {
		c[i] = a[i] + b[i];
	}
	c.flatten(len + 10);
	return c;
}
Bigint operator*(Bigint a, int b) {//重载运算符*
	Bigint c;
	int len = a.len;
	for (int i = 1; i <= len; i++) {
		c[i] = a[i] * b;
	}
	c.flatten(len + 40);
	return c;
}
int main() {//主函数
	int n, a, cnt = 0, t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cnt = 0;
		cin >> n >> a;
		Bigint ans(1);
		for (int j = 1; j <= n; j++) {
			ans = ans * j;
		}
		int len = ans.len;
		for (int j = 1; j <= len; j++) {
			if (ans[j] == a)cnt++;
		}
		cout << cnt << "\n";
	}
	return 0;
}

注意

题解仅供学习参考使用\color{red}{\text{题解仅供学习参考使用}}

抄袭、 复制题解， 以达到刷 AC 率 / AC 数量或其他目的的行为， 在洛谷是严格禁止的。
洛谷非常重视 学术诚信 。 此类行为将会导致您成为 作弊者\color{brown}{\text{作弊者}} 。 具体细则请查 看洛谷社区规则 。
提交题解前请务必阅读 《洛谷主题库题解规范》 。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...