题解 UVA10212 【The Last Non-zero Digit.】-阿里云开发者社区

开发者社区> 人工智能> 正文

题解 UVA10212 【The Last Non-zero Digit.】

简介: 题目链接 这题在学长讲完之后和看完题解之后才明白函数怎么构造。这题构造一个$f(n)$$f(n)$ $=$ $n$除以 $2^{a}$ $*$ $5^{b}$ ,$a$ , $b$ 分别是 $n$ 质因数分解后$2,5$的个数。

题目链接

这题在学长讲完之后和看完题解之后才明白函数怎么构造。

这题构造一个$f(n)$

$f(n)$ $=$ $n$除以 $2^{a}$ $*$ $5^{b}$ ,$a$ , $b$ 分别是 $n$ 质因数分解后$2,5$的个数。

然后就暴力算一算就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
//处理出来n的质因子中,x的个数。
int  prime(int n,int x)
{
    int res=0;
    while(n) res+=n/x,n/=x;
    return res;
}
//f(1)到f(n)中不以5结尾的奇数的个数
int expect_5_end_odd(int n,int x)
{
    if(!n) return 0;
    return n/10+(n%10>=x)+expect_5_end_odd(n/5,x);
}
//以5结尾的数的个数。
int expect_5_end(int n,int x)
{
    if(!n) return 0;
    return expect_5_end(n/2,x)+expect_5_end_odd(n,x);
}

int t[4][4]={
    6,2,4,8,//2^4 2 2^2 2^3 的最后一位
    1,3,9,7,//3^4 3 3^2 3^3 的最后一位
    1,7,9,3,//4……
    1,9,1,9//5……
};

signed main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        m=n-m;
        int prime_2=prime(n,2)-prime(m,2);
        int prime_3=expect_5_end(n,3)-expect_5_end(m,3);
        int prime_5=prime(n,5)-prime(m,5);
        int prime_7=expect_5_end(n,7)-expect_5_end(m,7);
        int prime_9=expect_5_end(n,9)-expect_5_end(m,9);
    
        if(prime_2<prime_5){puts("5");continue;}
    
        int res=1;
        if(prime_2>prime_5) res*=t[0][(prime_2-prime_5)%4];
        res=res*t[1][prime_3%4]*t[2][prime_7%4]*t[3][prime_9%4]%10;
        printf("%lld\n",res);
    }
    return 0;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章