博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU-1066 Last non-zero Digit in N!
阅读量:5877 次
发布时间:2019-06-19

本文共 3334 字,大约阅读时间需要 11 分钟。

详见代码:

方法一:

#include 
#include
#include
using namespace std;char s[1005];int len, Mp[25] = {
1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};// 直接计算出其循环节为20这里将0-19的列表于上,当N<5时直接输出,其余需要递归N/5因为这个表是删除了所有的5的倍数的 int slove(){ int ans = 1; while (len) { len -= !s[len-1]; ans = ans * Mp[s[1]%2*10+s[0]] % 10; // Mp中的值就是N%20的值,N%20只与十位和个位有关 for (int i = len-1, t = 0; i >= 0; --i) { // 除以5接着做 t = 10 * t + s[i]; // 其中t为余数 s[i] = t / 5; // num[i]处的商 t %= 5; // 新的余数 } } return ans;}int main(){ char t; while (scanf("%s", s) == 1) { len = strlen(s); for (int i = 0, j = len-1; i < (len>>1); ++i, --j) { t = s[i], s[i] = s[j], s[j] = t; } for (int i = 0; i < len; ++i) { s[i] -= '0'; } // 实现交叉以及去字符 printf("%d\n", slove()); } return 0; }

 

方法二:

#include 
#include
#include
#define MAXN 1005using namespace std;/*该题思路并没有想着去吧2,5提取出来,如果全部提取出来势必会去计算2的剩余量由于N很大,所以计算起来要用到两次大数计算除2以及除5后的值再相减再递归下去而只提取5,把2放入原数列进行计算,最后用除2抵消掉5的影响,这样就可以减少一次运算了,对于最有一个非零数,由于N!中2的个数始终多余5,所以在有剩余的情况下,最后这个非零位一定是一个偶数,因此也就能够快速计算出除2之后的结果了,2/2 = 6 (在不等于1的情况下就只有等于6(12/2)了), 4/2 = 2, 6/2 = 8,8/2 = 4, 我们就可以建立一个表递归下去了,也就最多抵消4个2,因为除2是有循环节的。在去除了5的干扰后,我们建立一个按照每10个元素分组的表来表示1*2*3*4*6*7*8*9的一个非零位{1, 1, 2, 6, 4, 4, 4, 8, 4, 6},5的倍数{5, 10, 15, 20, 25, 30...}在提取了5之后构成一个新的序列{1, 2, 3, 4, 5...} 给定一个N我们通过N/10来确定其在哪一个组,通过N%10来确定其在组内的哪一号元素,通过N/5来确定其递归下去的子序列 注意没有乘以5,10不代表不要统计其位置,我们还是要视作有5的存在,这样在%10计算的时候才能精确的找到其在一组中的位置,在确定好了其在哪一组的时候,又一个好的性质帮助了我们,因为每组的最后一个非零位是6,那么组与组进行相乘得到的非零位还是6所以我们就可以抛弃组数,组数大于1的话直接递归下去乘以6再乘以非零位的精确位置所存的序列再消去当前序列5的影响就完成了。F[x] = Mp [ (F[x/5] * 6 * table[x%10])%10 ] [(x/5)%4],大数的x/5通过乘以2除以10来得到%4的求解只与一个数的后两位有关 */char s[MAXN];int Mp[10][4] = { // 用来记录2,4,6,8分别在除二情况下的非零位变化 {
0}, {
0}, { 2, 6, 8, 4 }, {
0}, {
4, 2, 6, 8}, {
0}, {
6, 8, 4, 2}, {
0}, {
8, 4, 2, 6}, {
0}};int table[10] = {
1, 1, 2, 6, 4, 4, 4, 8, 4, 6};int solve(char *s){ int len, pos, c, k; for (int i = 1003; i >= 0; --i) { if (s[i] != -1) { len = i, pos = s[i]; break; } } if (len == 0) { if (s[0] < 5) return table[s[0]]; else return Mp[table[s[0]]][1]; } else { for (int i = len; i >= 0; --i) { s[i] *= 2; if (s[i+1] >= 10) { s[i] += s[i+1] / 10; s[i+1] %= 10; } } if (s[0] >= 10) { c = s[0] / 10; s[0] %= 10; for (int i = len; i >= 0; --i) { s[i] = s[i-1]; // 向后平移一个距离 } s[0] = c; } else { s[len] = -1; --len; } if (len > 0) { k = s[len] + s[len-1]*10; } else { k = s[len]; } return Mp[(solve(s) * 6 * table[pos])%10][k%4]; }}int main(){ memset(s, 0xff, sizeof (s)); while (scanf("%s", s) == 1) { int length = strlen(s); s[length] = -1; for (int i = 0; i < length; ++i) { s[i] -= '0'; } // 化为整数形式 printf("%d\n", solve(s)); memset(s, 0xff, sizeof(s)); } return 0;}

转载于:https://www.cnblogs.com/Lyush/archive/2012/08/10/2631545.html

你可能感兴趣的文章
Zeppelin的入门使用系列之使用Zeppelin运行shell命令(二)
查看>>
[Spark][Python]Spark Join 小例子
查看>>
form表单下的button按钮会自动提交表单的问题
查看>>
大战设计模式【11】—— 模板方法模式
查看>>
springBoot介绍
查看>>
Intellij IDEA 快捷键整理
查看>>
Redis 通用操作2
查看>>
11. Spring Boot JPA 连接数据库
查看>>
洛谷P2925 [USACO08DEC]干草出售Hay For Sale
查看>>
MapReduce工作原理流程简介
查看>>
那些年追过的......写过的技术博客
查看>>
小米手机解锁bootload教程及常见问题
查看>>
Python内置函数property()使用实例
查看>>
Spring MVC NoClassDefFoundError 问题的解决方法。
查看>>
CentOS 6.9配置网卡IP/网关/DNS命令详细介绍及一些常用网络配置命令(转)
查看>>
python基础教程_学习笔记19:标准库:一些最爱——集合、堆和双端队列
查看>>
C# 解决窗体闪烁
查看>>
CSS魔法堂:Transition就这么好玩
查看>>
【OpenStack】network相关知识学习
查看>>
centos 7下独立的python 2.7环境安装
查看>>