POJ1150he Last Non-zero Digit(组合）

链接

题意从尾部找第一个非0的数这样就可以考虑下怎样会形成0 这个都知道只有因子2和因子5相遇会形成0 那这样可以先把所有的2和5先抽出来，这样就保证了其它的数相乘就不会再出现0了这样就可以转换成尾数相乘的结果当然可能2的个数会剩余这一部分留到最后去算

step1 抽出所有的5和2 n!里因子x的个数求法： n/x+gn(n/x);

这样结果就为1 3 7 9 之一这样就需要求一下尾部3,,7,9的出现的次数，并且可以发现它们都是以4为周期的包括2

step2 尾部3 7 9出现的次数 f[n] + find(n/2) 因为抽走了2 x出现的次数g[n][x] = n/10+(n%10>=x)+ggn(n/5)因为抽走了5

最后再把2的影响补上

题意求N！/(n-m)! 因为N！包含（n-m)! 故可以通过各个数出现的次数相减求得最后的结果

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100000

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int o[][];

 int p[][];

 int gn(int n,int x)

 {

     if(n==)

     return ;

     return n/+(n%>=x)+gn(n/,x);

 }

 int ggn(int n,int x)

 {

     if(n==)

     return ;

     return gn(n,x)+ggn(n/,x);

 }

 int find0(int n,int x)

 {

     if(n==) return ;

     return n/x+find0(n/x,x);

 }

 int main()

 {

     int n,m;

     p[][] = ,p[][] = ,p[][] = ,p[][] = ;

     p[][] = ,p[][] = ,p[][] = ,p[][] = ;

     p[][] = ,p[][] = ,p[][] = ,p[][] = ;

     p[][] = ,p[][] = ,p[][] = ,p[][] = ;

     while(cin>>n>>m)

     {

         memset(o,,sizeof(o));

         m = n-m;

         o[][] = find0(n,);

         o[][] = find0(m,);

         o[][] = find0(n,);

         o[][] = find0(m,);

         o[][] = ggn(n,);

         o[][] = ggn(n,);

         o[][] = ggn(n,);

         o[][] = ggn(m,);

         o[][] = ggn(m,);

         o[][] = ggn(m,);

         o[][] -= o[][];

         o[][] -= o[][];

         int a = o[][]-o[][];

         int b = o[][]-o[][];

         int c = o[][]-o[][];

         int k = o[][]-o[][];

         int ans = ;

         if(a) ans*=p[][a%];

         if(b) ans*= p[][b%];

         if(c) ans*= p[][c%];

         if(k) ans*= p[][k%];

         cout<<ans%<<endl;

     }

     return ;

 }

巴特西

POJ1150he Last Non-zero Digit(组合）

最新文章

热门文章