N!的从最末一个非0位开始自低位向高位数的第M位 soj 1115

简介:

       阶乘

N的阶乘定义为:N!=N×(N-1)×……×2×1

请编写一个程序,输出N的阶乘的十进制表示中从最末一个非0位开始自低位向高位数的第M位。

其中:0<=N<=10000,1<=K<=5

例如:N=5,M=2,结果是1(5!=120)  N=8,M=3,结果为0(8!=40320)

 

输入:

第一行一个整数M (1<=M<=100),代表测试数据的个数;

接下来M行,每行两个整数N,K

输出:

     输出M行,每行一个整数,即测试数据的结果。

 

样例:

输入:

2
5 2
8 3

输出:

1
0

题意:很明了,就是求n!十进制表示中的从最末一个非0位开始自低位向高位数的第M位。有种思路就是将n!求出来,直接计算。

这种方法耗时828ms,memory 692K。

复制代码

   
   
#include < iostream >
#include
< string .h >
#include
< stdio.h >
#define MOD 10000
using namespace std;

int main( void )
{
int t;
scanf(
" %d " , & t);
while (t -- )
{
int i,j;
int n,k;
int digit,carry; //digit表示当前计算的值的位数,carry表示进位
int f[ 10000 ];
char s1[ 50000 ] = { ' \0 ' };
char s2[ 5 ];
long long temp;
f[
0 ] = 1 ;
digit
= 1 ;
scanf(
" %d%d " , & n, & k);
for (i = 2 ;i <= n;i ++ ) //求n!
{
carry
= 0 ;
for (j = 0 ;j < digit;j ++ )
{
temp
= ( long long )(f[j]) * ( long long )(i) + carry; //此处要用64位数据,防止数据溢出
f[j]
= temp % MOD;
carry
= temp / MOD;
}
while (carry)
{
f[digit
++ ] = carry % MOD;
carry
= carry / MOD;
}
}
i
= digit - 1 ;
while (f[i] == 0 )
{
i
-- ;
}
sprintf(s2,
" %d " ,f[i]);
strcat(s1,s2);
i
-- ;
for (;i >= 0 ;i -- ) //将结果存进字符数组中以便于处理
{
sprintf(s2,
" %04d " ,f[i]); //不足4位前面补0
strcat(s1,s2);
}
for (i = strlen(s1) - 1 ;i >= 0 ;i -- )
{
if (s1[i] != ' 0 ' )
break ;
}
printf(
" %d\n " ,s1[i - k + 1 ] - 48 );
}
return 0 ;
}
复制代码

下面是另外一种思路

由于是求最末一个非0位开始自低位向高位数的第M位,那么末尾的0则可以忽略掉,并且最多只需保存5位结果即可(M<=5)。

如:n!=A1A2A3..........Ai000000000 Ai!=0

则只需取A(i+4)A(i+3)A(i+2)A(i+1)Ai这5位即可.

耗时0ms,memory 580K,明显效率高很多。

复制代码

   
   
#include < iostream >
#define MOD 100000
using namespace std;

int main( void )
{
int t;
scanf(
" %d " , & t);
while (t -- )
{
int n,k;
int i,ans;
ans
= 1 ;
scanf(
" %d %d " , & n, & k);
for (i = n;i >= 2 ;i -- )
{
ans
*= i;
while (ans % 10 == 0 ) // 消除末尾的0
{
ans
/= 10 ;
}
if (ans >= MOD) // 只需保存末尾5位数字即可
ans %= MOD;
}
for (i = 1 ;i < k;i ++ )
{
ans
= ans / 10 ;
}
ans
= ans % 10 ;
printf(
" %d\n " ,ans);
}
return 0 ;
}
复制代码

相关文章
|
12月前
|
IDE Java 开发工具
深入探索安卓应用开发:从环境搭建到第一个"Hello, World!"应用
本文将引导读者完成安卓应用开发的初步入门,包括安装必要的开发工具、配置开发环境、创建第一个简单的安卓项目,以及解释其背后的一些基本概念。通过一步步的指导和解释,本文旨在为安卓开发新手提供一个清晰、易懂的起点,帮助读者顺利地迈出安卓开发的第一步。
374 65
|
12月前
Saga模式在分布式系统中如何保证事务的隔离性
Saga模式在分布式系统中如何保证事务的隔离性
214 7
|
9月前
|
机器学习/深度学习 人工智能 算法
【AI系统】推理流程全景
本文概述了神经网络模型在云侧和边缘侧部署的特点与挑战。云侧部署凭借强大的计算能力和集中的数据管理,适合高吞吐量应用,但面临高成本、网络延迟等问题;边缘侧部署则通过模型优化和硬件加速降低延迟和能耗,适用于资源受限的环境,但存在算力限制、数据分散等挑战。两种方式各有优劣,需根据实际需求选择。
307 5
|
存储 缓存 NoSQL
如何解决Ubuntu server 下 Redis安装报错:“You need tcl 8.5 or newer in order to run the Redis test”.
如何解决Ubuntu server 下 Redis安装报错:“You need tcl 8.5 or newer in order to run the Redis test”.
707 0
|
SQL 运维 监控
MSSQL性能调优深度解析:索引优化策略、SQL查询优化技巧与高效并发管理实践
在Microsoft SQL Server(MSSQL)的运维与优化领域,性能调优是确保数据库高效运行、满足业务需求的关键环节
|
11月前
|
Java
JVM进阶调优系列(5)CMS回收器通俗演义一文讲透FullGC
本文介绍了JVM中CMS垃圾回收器对Full GC的优化,包括Stop the world的影响、Full GC触发条件、GC过程的四个阶段(初始标记、并发标记、重新标记、并发清理)及并发清理期间的Concurrent mode failure处理,并简述了GC roots的概念及其在GC中的作用。
|
存储 程序员 C语言
|
机器学习/深度学习 传感器 数据采集
【BP回归预测】基于BP神经网络的回归预测附matlab完整代码
【BP回归预测】基于BP神经网络的回归预测附matlab完整代码
|
资源调度 前端开发
文本,vitepress的使用,如何使用vitevitepress没有config.js该怎么办?这里使用vitepress进行手动配置,参考只爭朝夕不負韶華的文章
文本,vitepress的使用,如何使用vitevitepress没有config.js该怎么办?这里使用vitepress进行手动配置,参考只爭朝夕不負韶華的文章
|
机器学习/深度学习 数据采集
R语言逻辑回归、GAM、LDA、KNN、PCA主成分分类分析预测房价及交叉验证
上述介绍仅为简要概述,每个模型在实施时都需要仔细调整与优化。为了实现高度精确的预测,模型选择与调参是至关重要的步骤,并且交叉验证是提升模型稳健性的有效途径。在真实世界的房价预测问题中,可能还需要结合地域经济、市场趋势等宏观因素进行综合分析。
271 3