UVa 10061 How many zero's and how many digits?-白红宇

UVa 10061 How many zero's and how many digits?

阅读量：5316 次

发布时间：2019-06-14

本文共 5044 字，大约阅读时间需要 16 分钟。

方法： factorial mod， logarithm

求trailing zeros，其实就是factorial mod 的应用，

求长度，利用log 函数。需要注意的是，答案为int(log(n!)/log(b)) + 1, 比如 a = 2, b = 2, 长度为2.

code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          #include 
                          
                           #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))#define DFOR(a,b,c) for (int (a)=(b);(a)>=(c);--(a))#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))#define FOREACH(a,b) for (auto &(a) : (b))#define rep(i,n) FOR(i,0,n)#define repn(i,n) FORN(i,1,n)#define drep(i,n) DFOR(i,n-1,0)#define drepn(i,n) DFOR(i,n,1)#define MAX(a,b) a = Max(a,b)#define MIN(a,b) a = Min(a,b)#define SQR(x) ((LL)(x) * (x))#define Reset(a,b) memset(a,b,sizeof(a))#define fi first#define se second#define mp make_pair#define pb push_back#define all(v) v.begin(),v.end()#define ALLA(arr,sz) arr,arr+sz#define SIZE(v) (int)v.size()#define SORT(v) sort(all(v))#define REVERSE(v) reverse(ALL(v))#define SORTA(arr,sz) sort(ALLA(arr,sz))#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))#define PERMUTE next_permutation#define TC(t) while(t--)#define forever for(;;)#define PINF 1000000000000#define newline '\n'#define test if(1)if(0)cerrusing namespace std; using namespace std;typedef vector
                           
                             vi;typedef vector
                            
                              vvi;typedef pair
                             
                               ii;typedef pair
                              
                                dd;typedef pair
                               
                                 cc;typedef vector
                                
                                  vii;typedef long long ll;typedef unsigned long long ull;typedef pair
                                 
                                   l4;const double pi = acos(-1.0);int a, b;bitset<2000001> vis(0);ll primes[2000001];int pcnt = 0;// said to be O(n) prime generatingvoid init(){ for (ll i = 2; i <= 2e6; ++i) { if (!vis[i]) primes[pcnt++] = i; for (int j = 0; j < pcnt && i * primes[j] <= 2e6; ++j) { vis[j*primes[j]] = true; if (i % primes[j] == 0) break; } }}int main(){ init(); while (cin >> a >> b) { int ans = 1e9; int B = b; for (int i = 0; i < pcnt && b >= primes[i]; ++i) { if (b % primes[i]) continue; int bcnt = 0; while (b % primes[i] == 0) { b /= primes[i]; bcnt += 1; } int fcnt = 0; int cur = a; while (cur) { cur /= primes[i]; fcnt += cur; } ans = min(ans, fcnt/bcnt); } double len = 0; for (int i = 2; i <= a; ++i) { len += log(1.0*i); } cout << ans << " " << max((int)(len/log(B)+1),1) << newline; }}

（我的笨办法）求trailing zero's 的长度，用一个数组记录下factorial里各个prime的power，然后用另一个数组记录下b里各个prime的power，然后求解。

code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          #include 
                          
                           #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))#define DFOR(a,b,c) for (int (a)=(b);(a)>=(c);--(a))#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))#define FOREACH(a,b) for (auto &(a) : (b))#define rep(i,n) FOR(i,0,n)#define repn(i,n) FORN(i,1,n)#define drep(i,n) DFOR(i,n-1,0)#define drepn(i,n) DFOR(i,n,1)#define MAX(a,b) a = Max(a,b)#define MIN(a,b) a = Min(a,b)#define SQR(x) ((LL)(x) * (x))#define Reset(a,b) memset(a,b,sizeof(a))#define fi first#define se second#define mp make_pair#define pb push_back#define all(v) v.begin(),v.end()#define ALLA(arr,sz) arr,arr+sz#define SIZE(v) (int)v.size()#define SORT(v) sort(all(v))#define REVERSE(v) reverse(ALL(v))#define SORTA(arr,sz) sort(ALLA(arr,sz))#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))#define PERMUTE next_permutation#define TC(t) while(t--)#define forever for(;;)#define PINF 1000000000000#define newline '\n'#define test if(1)if(0)cerrusing namespace std; using namespace std;typedef vector
                           
                             vi;typedef vector
                            
                              vvi;typedef pair
                             
                               ii;typedef pair
                              
                                dd;typedef pair
                               
                                 cc;typedef vector
                                
                                  vii;typedef long long ll;typedef unsigned long long ull;typedef pair
                                 
                                   l4;const double pi = acos(-1.0);int a, b;int d[2000001] = {0};int cnt[2000001];int fcnt[2000001];void init(){ d[1] = 1; for (ll i = 2; i <= 2e6; ++i) { if (!d[i]) {d[i] = (int)i; for (ll j = i*i; j <= 2e6; j += i) d[j] = (int) i; } }}int main(){ init(); while (cin >> a >> b) { Reset(cnt, 0); int ans = 0; double len = 0; for (int i = 2; i <= a; ++i) { len += log(1.0*i); int cur = i; while (cur != 1) { cnt[d[cur]] += 1; cur /= d[cur]; } } Reset(fcnt, 0); int cur = b; while (cur != 1) { fcnt[d[cur]] += 1; cur /= d[cur]; } ans = 1e9; for (int i = 2; i <= b; ++i) if (fcnt[i]) { ans = min(ans, cnt[i]/fcnt[i]); //cerr << i << " " << cnt[i] << " " << fcnt[i] << newline; } cout << ans << " " << max((int)(len/log(b)+1),1) << newline; }}