点击打开链接poj 1150
思路:组合数学+排列组合
分析:
1 求排列数A(n , m)的末尾第一个非0数。
2 总结一下,求n!最后一个非0位的步骤如下:
step1:首先将n!中所有2,5因子去掉;
step2:然后求出剩下的一串数字相乘后末尾的那个数。
step3:由于去掉的2比5多,最后还要考虑多余的那部分2对结果的影响。
step4:output your answer!
详见
点击打开链接
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int a , b;
/*找到2 3 7 9的n次方后的最后一位的循环节*/
int hash[4][4] ={
{6 , 2 , 4 , 8},/*2 4 8 16,16的时候是6但是下标只到3所以把6放在第一个位置,以下类似*/
{1 , 3 , 9 , 7},
{1 , 7 , 9 , 3},
{1 , 9 , 1 , 9}
};
/*求出含有因子x的个数*/
int getFactor(int n , int m){
if(m == 0)
return 0;
return m/n+getFactor(n , m/n);
}
/*求奇数系列*/
int getOdd(int n , int m){
if(m == 0)
return 0;
return m/10+(m%10 >= n)+getOdd(n , m/5);
}
/*对序列求3 7 9的个数*/
int getAll(int n , int m){
if(m == 0)
return 0;
return getAll(n , m/2)+getOdd(n , m);
}
int main(){
int two , three , five , seven , nine;
while(scanf("%d%d" , &a , &b) != EOF){
if(!a || !b){
printf("1\n");
continue;
}
two = getFactor(2 , a)-getFactor(2 , a-b);
five = getFactor(5 , a)-getFactor(5 , a-b);
three = getAll(3 , a)-getAll(3 , a-b);
seven = getAll(7 , a)-getAll(7 , a-b);
nine = getAll(9 , a)-getAll(9 , a-b);
two -= five;
int ans = 1;
/*当含有2和含有5的数相同时候对结果是没有影响的*/
if(two)
ans *= hash[0][two%4];
ans *= hash[1][three%4];
ans *= hash[2][seven%4];
ans *= hash[3][nine%4];
printf("%d\n" , ans%10);
}
return 0;
}
分享到:
相关推荐
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
poj 2196 Specialized Four-Digit Numbers.md
POJ水题集-----50道左右-----增加自信啊..
西北工业大学-c语言-POJ-题目及答案-第七季.doc
用Java代码实现POJ(PKU)上题2494!
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
很有用的解题报告。。是acm初级提高的必备资料。。。。。
poj 1028 Web Navigation 的代码,已通过!
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
poj题目分类--acmer做题极有用资源
北大POJ1163-The Triangle 解题报告+AC代码