因为数据范围较大,阶乘直接计算会溢出。所以不能直接计算阶乘再输出右侧第一个非零数字。
开始想着,每次计算结果去除右侧的所有 0。 发现还会超时(其实还是溢出了)
那就把每次的结果保留后面 7 位不为 0 的数字。
为什么不能保留 1 位,2 位呢?因为 n 的范围是 1 ~ 1000,乘积的最右侧非零数字的有时候不止受 1 位影响。
比如:
-
$\color{red}{24!= 620448401733239439360000,最右侧非零数字为:6。}$
-
$\color{red}{25!= 15511210043330985984000000。最右侧数字为4。不是 6 * 25 结果的最右侧。}$
-
$\color{red}{6 * 25 的结果为 150,而 36 * 25 的结果为 900, 936 * 25 的结果为 23400。}$
-
$\color{red}{所以只保留个位不行。}$
为什么是 7 位呢?因为数据范围是 1 ~ 1000。两数相乘的结果,最多有 6 个零。所以保留 7 位肯定没问题。(这里可能还有更好的解释)
少保留几位可以不? 其实也可以,保留 3 位也正确的。
#include <iostream>
using namespace std;
int main()
{
int n;
int res = 1;
cin >> n;
for (int i = 1; i <= n; i++)
{
res = res * i;
while (!(res % 10))//去除末尾 0
{
res = res / 10;
}
res = res % 10000000;//保留右侧 7 位非零数字
}
cout << res % 10;//输出右侧第一个非零数字
}
有问题直接评论即可。
求点赞~
这代码,洛谷上过不去
可能他们用例比较强,把0多保留几位就行
改成long long才可以
保留7位不行啊,大佬。
while (!(res % 10))//去除末尾 0
{
res = res / 10;
}
res = res % 10000000;//保留右侧 7 位非零数字
大佬,这样写怎么不对啊,就末尾如果是0,就除10再取余
应该是溢出了,即便把末尾所有 0 去掉,如果 n 比较大,也会溢出
res*=i%10
和res=res*i%10
这两种表达式 还是不一样吗。。。查一下优先级就知道了,想要一样可以试试加括号
是不一样的,% 优先级介于 * 和 *= 之间
这段代码没问题,你应该是其他部分写错了
还是y总的方法好,,
res = res % 10000000;//保留右侧 7 位非零数字
七位的话测试数据888报错
取3到6位最好
应该没有问题吧,题主的不是ac了吗?
还有就是,不可以把
while (!(res % 10))//去除末尾 0 { res = res / 10; }
提到for外吗....
不行吧,要是
res % 1e7 == 0
就只能返回0
了会溢出
为什么最少保留三位也行呢?
是不是因为 两个不能被10整除的数 的 乘积 最少不能能被1000整除 25*26=600 所以两位不行
其实我这里也没完全搞明白,晚上看看y总讲
同问,兄弟会了吗。。?
谢谢,我就只保存了两位管不得错误了
妙啊
后来调试了,保留 4 位就可以,但是我想不通为什么。。
我甚至保留3位就ac了
这个需要再再想想
除到long long范围内就行了吧
巨巨,你这个 3625 和 96325 是不是算错了啊?
是的,写错了,谢谢。改正了
嗯嗯