博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA-10212 The Last Non-zero Digit. 分解质因子+容斥定理
阅读量:5838 次
发布时间:2019-06-18

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

这个是参考了别人之后的代码,POJ上0MS过了。Orz......对于一个序列在提取了2,5之后,例如1,2,3,4,5,6,7,8,9,10,我们可以将其中的奇数和偶数分开来对待,对于偶数序列2,4,6,8,10由于原序列会被提取出2,所以就退化成了1,2,3,4,5,这个奇数序列,对于奇数序列1,3,5,7,9我们就可以来统计3,5,7的数量了,同样出现的次数是总长度N=10除以10(单位出现区间)再判定N%10是否大于要求得数,对于这个奇数序列由于5是要被提取的,所以又变成了1这个序列,更多数可能更好看了。如此递归下去便行了。

代码如下:

#include 
#include
#include
using namespace std;int N, M, rec[4][4] = { {
6, 2, 4, 8}, {
1, 3, 9, 7}, {
1, 7, 9, 3}, {
1, 9, 1, 9}};int Get2(int x){ if (!x) return 0; return x/2+Get2(x/2);}int Get5(int x){ if (!x) return 0; return x/5+Get5(x/5);}int GetOdd(int x, int Base){ if (!x) return 0; return x/10 + (x%10 >= Base) + GetOdd(x/5, Base);}// 传进去的还是一个完整的序列,该函数的功能在于得到其偶数序列的性质 int GetEven(int x, int Base){ if (!x) return 0; return GetEven(x/2, Base) + GetOdd(x, Base);}int main(){ int n2, n3, n5, n7, n9, m2, m3, m5, m7, m9, ret; while (scanf("%d %d", &N, &M) == 2) { ret = 1; M = N - M; n2 = Get2(N), m2 = Get2(M); n5 = Get5(N), m5 = Get5(M); n2 -= m2, n5 -= m5; if (n2 >= n5) { n2 -= n5, n5 = 0; } else { puts("5"); continue; } n3 = GetEven(N, 3), m3 = GetEven(M, 3); n7 = GetEven(N, 7), m7 = GetEven(M, 7); n9 = GetEven(N, 9), m9 = GetEven(M, 9); n3 = (n3-m3)%4, n7 = (n7-m7)%4, n9 = (n9-m9)%4; if (n2) ret *= rec[0][n2%4]; ret *= rec[1][n3] * rec[2][n7] * rec[3][n9]; printf("%d\n", ret % 10); } return 0; }

 

 

我的这个写法并不是最好的,POJ上的1150是没方法过的,UVA上的时限相对比较松。能在POJ上过的基本0MS,这段代码UVA上跑了7MS多。

解释见代码:

#include 
#include
#include
using namespace std;/* 计算排列数A(M,N)的最后一位非零位,A(M, N) = N! / (N-M)!令 M = N - M,则问题转化为 N! / M!,从质因子的角度出发,我们一定能够得到 N! 的各项质因子的数量都一定 大于等于 M!,如果N比较小的话我们找可以出两者所有的质因子2,5的数量,以及以3,7,9结尾的质因子,再进行相消,最后得到结果。如果N较大的话,就只关心质因子2,5的数量,相当于我们对于 N!写成 N! = 2^e1 * 5^e2 * x1 * x2 * x3 * ...,对于提出了2, 5的序列,我们又可以将其视为1*2*3*4*...N/2(N/5)的一个序列(原序列为2*4*6*8*10*...或者是5*10*15*20*...),对于这样一个重新编排的的序列,我们可以继续统计出2,5,我们还可以继续进行重拍,并且一直进行下去,提取出2,5后我们面对就是一系列的只含有1,3,7,9的序列,因此我们还需要统计出它们(非质因子分解后)分别的数量,我们可以知道已这些结尾的数都是每10个数出现一次,所以我们只需要对整个序列的长度除以10来得到,在重排除以2,5后的序列时要注意用容斥定理减去重复计算的 */ int N, M, rec[4][4] = { {
6, 2, 4, 8}, {
1, 3, 9, 7}, {
1, 7, 9, 3}, {
1, 9, 1, 9}};int Get2(int x){ if (!x) return 0; return x/2+Get2(x/2);}int Get5(int x){ if (!x) return 0; return x/5+Get5(x/5);}int Get3(int x){ if (!x) return 0; return x/10 + (x%10>=3) + Get3(x/2) + Get3(x/5) - Get3(x/10);}int Get7(int x){ if (!x) return 0; return x/10 + (x%10>=7) + Get7(x/2) + Get7(x/5) - Get7(x/10);}int Get9(int x){ if (!x) return 0; return x/10 + (x%10>=9) + Get9(x/2) + Get9(x/5) - Get9(x/10);}int main(){ // 对2,5处理只是为了把后面的零全部去除,最后一定只剩下n2 // n2 表示的就是最有对最后一位非零位有贡献的因子2的个数 // 2,3,7,9循环节的最小公倍数为4 int n2, n3, n5, n7, n9, m2, m3, m5, m7, m9, ret; while (scanf("%d %d", &N, &M) == 2) { ret = 1; M = N - M; n2 = Get2(N), m2 = Get2(M); n5 = Get5(N), m5 = Get5(M); n2 -= m2, n5 -= m5; if (n2 >= n5) { n2 -= n5; n5 = 0; } else { n5 -= n2; n2 = 0; } n3 = Get3(N), m3 = Get3(M); n7 = Get7(N), m7 = Get7(M); n9 = Get9(N), m9 = Get9(M); n3 -= m3, n7 -= m7, n9 -= m9; if (n2) { ret *= rec[0][n2%4]; } if (n5) { ret *= 5; } n3 %= 4, n7 %= 4, n9 %= 4; ret = ret * rec[1][n3] * rec[2][n7] * rec[3][n9]; printf("%d\n", ret % 10); } return 0; }

转载于:https://www.cnblogs.com/Lyush/archive/2012/08/09/2629882.html

你可能感兴趣的文章
Jira迁移及内存调整
查看>>
Exchange Server 2010 SP2 新功能简述
查看>>
使用wxWidgets for C++从资源文件中静态装载图像
查看>>
提高数据库安全性的办法
查看>>
工作流编程循序渐进(8:状态机工作流)
查看>>
3.VMware View 4.6安装与部署-connection server(View Standard Server)
查看>>
Lync Server 2013 实战系列之六:标准版-安装和更新LyncServer 系统
查看>>
MariaDB日志审计 帮你揪出内个干坏事儿的小子
查看>>
Reporting Services目录临时数据库文件存在
查看>>
一个Windows Mobile, Windows Embedded CE工程师的找工经历(一)
查看>>
终于有了MSDN上的Blog
查看>>
PHPUnit学习03---使用Mock对象解决测试依赖
查看>>
java类型与Hadoop类型之间的转换
查看>>
允许SQL Server 2005远程连接
查看>>
微软为asp.net ajax和jquery创建了CDN
查看>>
Chris:怎样成为一名Android应用开发
查看>>
常见的makefile写法【转】
查看>>
emmet,jade,haml, slim,less,sass,coffeescript等的实战优缺点
查看>>
和菜鸟一起学linux总线驱动之初识spi驱动数据传输流程【转】
查看>>
WorkFlow设计篇Step.4—异常处理(续)-WF4.0
查看>>