HDU 1042 N！大数乘法

川长思鸟来 2022-04-23 10:52 380阅读 0赞

# N! #

Time Limit : 10000/5000ms (Java/Other)   Memory Limit : 262144/262144K (Java/Other)

Total Submission(s) : 69   Accepted Submission(s) : 38

### Problem Description ###

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

### Input ###

One N in one line, process to the end of file.

### Output ###

For each N, output N! in one line.

### Sample Input ###

1
    2
    3

### Sample Output ###

1
    2
    6

### Author ###

JGShining（极光炫影）

[题目链接][Link 1]

思路：用一个N长的数组存数字，a\[0\]表示个位。分别用 i (0~10000)乘以该数组，对数组进行修正。循环遍历 i，从2~n，输出数组即为结果！奈斯！

#include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    #define N 100000
    int main(){
    	ios::sync_with_stdio(false);
    	int n, carry;
    	int i, j, k;
    	long long int a[N];
    	while(cin >> n){
        	memset(a, 0, sizeof(a));
    	 	if(n >= 0) a[0] = 1;
    	 	for(i = 2;i <= n; i++){
    			for(j = N-1; j >= 0; j--)
    	 	   		if(a[j] != 0)
    	 	   		  break; //此时的 j为首位不为 0 的位置	 	
    	 	   	for(k = 0; k <= j; k++)
    	 	   		a[k] *= i; //a[k] 每一个元素都乘以 i 
    			carry = 0; // 为进位使用 
    			for(k = 0; k <= j; k++){
    				int temp = carry;
    				carry = (a[k] + temp) / 10;
    				a[k] = (temp + a[k]) % 10; //每次取当前位置a[k]+carry的个位作为 a[k] 
    			}
    			if(carry != 0 && carry > 0 && carry < 10) 
    				a[k] = carry;  // 循环结束前做了一次k++，故此处无需 k++，取到最后carry在 1~9 之间 
    			else{	// carry >= 10 
    				while(carry){  
    					a[k] = carry % 10;
    					k ++;
    					carry /= 10;
    				}
    			}
    		}	//计算结束
    		//从后往前依次输出数组元素，即该结果 n!			
    		for(i = N-1; i >=0; i--){
    			if( a[i] != 0) {
    				for(j = i; j >= 0; j--)
    					cout << a[j];
    					cout << endl;
    					break;
    			}
    		}
    	}
    	 return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1042