The number of digits of power and factorial

The author summarizes his ideas , There are two ways to solve the length of exponentiation , Find the length of factorial . So as to solve the problem like
“ Please count a Of b How many digits are there in the power ( Decimal numbers )!”
“N! (N The factorial ) Is a very large number , The formula is ：N! = N * (N - 1) * (N - 2) * … * 2 * 1). Now we need to know N! How many? （ Decimal system ） position .” And so on .

Method 1 ： call log10() function

Solve the number of factorial digits

int digit(int n)// Counting n The length of the factorial of 
{
    
   double length = 0;
   for(int i =1;i<=n;++i)
	   length += log10((double)i);
   // Here is Jinyi method ,length by double Type variable , There is no absolute integer value , It can only be approximated to an integer 
   return (int)(length+1); 
}

Solve the number of exponents

It's similar to solving the number of factorials , The difference lies in two variables

int digit(int a, int b)// Counting a Of b Length of power 
{
    
   double length = 0;
   for(int i =1;i<=b;++i)
	   length += log10((double)a);
   // Here is Jinyi method ,length by double Type variable , There is no absolute integer value , It can only be approximated to an integer 
   return (int)(length+1); 
}

Method 2 ： Set up sentry, right 10 Surplus method

Solve the number of factorial digits

Title source

http://acm.nefu.edu.cn/problemShow.php?problem_id=65

Description

N! (N The factorial ) Is a very large number , The formula is ：N! = N * (N - 1) * (N - 2) * … * 2 * 1). Now we need to know N! How many? （ Decimal system ） position .

Input

Enter... On each line 1 A positive integer N.0 < N < 1000000

Output

For each N, Output N! Of （ Decimal system ） digit .

Sample Input

1
3
32000
1000000

Sample Output

1
1
130271
5565709

Ideas

Set a large number , In the process of constantly updating factorials, once this number is exceeded dui10 Remainder , Update the length at the same time , To prevent factorial crossing .

 according to 0 < N < 1000000 , I define int64_t M = 1e10
const int64_t M = 1e10; 

AC Code

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<inttypes.h>
using namespace std;
int64_t sum = 1;const int M = 1e10;// Set up a sentry 
int main(){
    
    int n;//n<=1000000
    while(cin>>n){
    
		if(n<=3) cout<<1<<endl;//0,1,2,3 The number of factorial digits of is 1 position 
		else{
    
			int length = 0;sum = 1;//length Is the length of factorial 
			for(int i=2;i<=n;i++){
    
				while(sum > M){
    
					sum /= 10;
					length++;
				}
				sum *= i;
			}
			while(sum){
    
				sum /= 10;
				length++;
			}
			cout<<length<<endl;
		}
    }
    return 0;
}

Solve the length of power

Compared with the above code, it only changes a little 、

Title source

http://acm.nefu.edu.cn/problemShow.php?problem_id=94

Description

Please count a Of b How many digits are there in the power ( Decimal numbers )!

Input

Multiple groups of input data , The two positive integers in each group are a and b, among (1<=a<=10000,1<=b<=10000)

Output

Output a^b(a Of b The next power ) How many digits are there in the value of ?

Sample Input

2 3
1 1
10 5

Sample Output

1
1
6

AC Code

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<inttypes.h>
using namespace std;
int64_t sum = 1;const int M = 1e10;
// Calculation a Of b How many digits are there in the power   among (1<=a<=10000,1<=b<=10000)
int64_t getpowLen(int a,int b)
{
    
	if(b == 0)  return 1;
	int64_t ans = 0;int64_t sum = 1;//ans Storage length ,sum Used to update power 
	for(int i=1;i<=b;i++){
    
		while(sum > M){
    
			sum /= 10;
			ans++;
		}
		sum *= a;
	}
	while(sum){
     // Find the last remaining length 
		sum /= 10;
		ans++;
	}
	return ans;
}
int main(){
    
    int a,b;
    while(cin>>a>>b)
		cout<<getpowLen(a,b)<<endl;
    return 0;
}

summary

The author believes that using log10() Functions are more accurate , At the same time, it also has a new application to the basic theorem of arithmetic .
For the second algorithm , If the title gives n The maximum length of is 10¹⁸, Then the Sentry will explode int64_t The range that can be expressed , Cannot store sentinel , In this case, the second method is also powerless .