poj 1150 The Last Non-zero Digit

 /**
大意: 求A(n,m)的结果中从左到右第一个非零数
思路: 0是由2*5的得到的,所以将n!中的2,5约掉可得(2的数目比5多,最后再考虑进去即可)
那n!中2 的个数怎么求呢?
int get2(int n){
if(n==0)
return 0;
return n/2+get2(n/2);
}
eg: 1*2*3*4*5*6*7*8*9*10 约去2,5可得,,1*1*3*1*1*3*7*1*9*1
所以最后肯定是3,7,9.。的数列,,那么在最后的数列中3,7,9,有多少个呢?
可以这样考虑: 1,2,3,4,5,6,7,8,9,10 可以分为奇偶数列 即 1,3,5,7,9 2,4,6,8,10===>2*(1,2,3,4,5)
这就出现了递归,,g(n) = g(n/2)+f(n) { f(n)为奇数列 }
那在奇数列中怎么找3,7,9 的个数呢?
1,3,5,7,9,11,13,15,17,19 有可以再分 1,3,7,9,11,13,17,19 ///5,15,25 ====〉5*(1,3,5)
这里有出现了递归,,f(n,x) = n/10 + (n%10>=x) + f(n/5,x)
**/ #include <iostream>
using namespace std; int s[][]={
{,,,},{,,,},{,,,},{,,,}
};
int get2(int n){
if(n==)
return ;
return n/+get2(n/);
} int get5(int n){
if(n==)
return ;
return n/+get5(n/);
} int get(int n,int x){
if(n==)
return ;
return n/+(n%>=x)+get(n/,x);
} int getx(int n,int x){
if(n==)
return ;
int res =;
res = getx(n/,x)+get(n,x);
return res;
} int main()
{
int n,m;
while(cin>>n>>m){
int num2 = get2(n)-get2(n-m);
int num5 = get5(n)-get5(n-m);
int num3 = getx(n,)-getx(n-m,);
int num7 = getx(n,)-getx(n-m,);
int num9 = getx(n,)-getx(n-m,);
if(num2<num5){
cout<<<<endl;
continue;
}else{
int res =;
if(num2!=num5){
num2 = num2-num5;
res = res*s[][num2%];
res = res%;
}
res *= s[][num3%];
res %=;
res *= s[][num7%];
res %=;
res *= s[][num9%];
res = res%;
cout<<res<<endl;
}
}
return ;
}
上一篇:IOS 生成设备唯一标识


下一篇:pymysql操作数据库