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

[复制链接]
385|8
手机看帖
扫描二维码
随时随地手机跟帖
functions|  楼主 | 2019-9-14 18:09 | 显示全部楼层 |阅读模式
                                     阶乘
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)

使用特权

评论回复

相关帖子

functions|  楼主 | 2019-9-14 18:09 | 显示全部楼层
输入:

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

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

使用特权

评论回复
functions|  楼主 | 2019-9-14 18:09 | 显示全部楼层
输出:

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

使用特权

评论回复
functions|  楼主 | 2019-9-14 18:10 | 显示全部楼层
样例:

输入:

2
5 2
8 3

输出:

1
0

使用特权

评论回复
functions|  楼主 | 2019-9-14 18:10 | 显示全部楼层
题意:很明了,就是求n!十进制表示中的从最末一个非0位开始自低位向高位数的第M位。有种思路就是将n!求出来,直接计算。

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

使用特权

评论回复
functions|  楼主 | 2019-9-14 18:10 | 显示全部楼层
#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;
}

使用特权

评论回复
functions|  楼主 | 2019-9-14 18:11 | 显示全部楼层
下面是另外一种思路

由于是求最末一个非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,明显效率高很多。

使用特权

评论回复
functions|  楼主 | 2019-9-14 18:11 | 显示全部楼层
#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;
}

使用特权

评论回复
functions|  楼主 | 2019-9-14 18:11 | 显示全部楼层
作者:Matrix海子
    
出处:http://www.cnblogs.com/dolphin0520/
    
本博客中未标明转载的**归作者Matrix海子和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在**页面明显位置给出原文连接,否则保留追究法律责任的权利。

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

39

主题

446

帖子

1

粉丝