title: ‘阶乘 第一个不是零的数字’date: 2020-03-16 21:56:25
tags: [蓝桥杯]
published: true
hideInList: false
feature:
isTop: false

  1. /*试题 算法训练 P0505
  3. 资源限制
  4. 时间限制：1.0s   内存限制：256.0MB
  5. 　　一个整数n的阶乘可以写成n!，它表示从1到n这n个整数的乘积。阶乘的增长速度非常快，例如，13！就已经比较大了，已经无法存放在一个整型变量中；而35！就更大了，它已经无法存放在一个浮点型变量中。因此，当n比较大时，去计算n!是非常困难的。幸运的是，在本题中，我们的任务不是去计算n!，而是去计算n!最右边的那个非0的数字是多少。例如，5！=1*2*3*4*5=120，因此5!最右边的那个非0的数字是2。再如，7！=5040，因此7！最右边的那个非0的数字是4。再如，15！=
  6. 1307674368000，因此15！最右边的那个非0的数字是8。请编写一个程序，输入一个整数n(0<n<=100)，然后输出n!最右边的那个非0的数字是多少。
  7. 输入：
  8. 　　7
  9. 输出：
  10. 　　4
  11. */
  12. #include <iostream>
  13. using namespace std;
  14. int delZero(int i) {
  15.     while (i % 10 == 0) {
  16.         i /= 10;
  17.     };
  18.     return i;
  19. }
  20. int main() {
  21.     int n;
  22.     cin >> n;
  23.     int ans = 1;;
  24.     for (int i = 1; i <= n; i++) {
  25.         ans *= i;
  26.         ans = delZero(ans);
  27.         ans = ans % 1000;
  28.     }
  29.     cout <<ans%10;
  30.     return 0;
  31. }

因为这道题n的范围是 n<100 所以对1000求余是可以得出正确答案的，如果更大可以用数组模拟乘法来做

#include <iostream>
#include <string.h>
using namespace std;
int a[10005];
int main() {
    long n;
    memset(a, 0, sizeof(a));
    cin >> n;
    a[0] = 1;
    int s, c = 0;  // c 进位
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10000; j++) {
            s = a[j] * i + c;
            a[j] = s % 10;
            c = s / 10;
        }
    }
    for (int i = 0;; i++) {
        if (a[i] != 0) {
            cout << a[i];
            break;
        }
    }
    return 0;
}