原题

给定长度为 n 的整数序列 a_1,a_2,...,a_n，求乘积 a_1×a_2×...×a_n 的十进制表示中最后一位非零数字。

输入第一行是整数 n (1<=n<=10^6)；第二行是 n 个整数 a_1,...,a_n (1<=a_i<=10^9)。

输出一行一个整数，表示答案。

样例 1：

输入
2
2 3

输出
6

样例 2：

输入
1
100

输出
1

题解

MC0436 数字相乘（C++17）

给定 n 个正整数，求它们乘积的十进制表示中最后一位非零数字。乘积很快会溢出，但题目只关心删去末尾所有 0 后的个位。

先只看末尾的 0 从哪里来。一个 0 就是一组 2×5，其他因子不会让十进制末尾多出 0。因此没有必要真的维护整个乘积，只要统计其中的 2 和 5。

因此对每个 a_i 拆出全部因子 2 和 5：

$$ a_i=2^{x_i}5^{y_i}r_i, $$

其中 r_i 不含因子 2、5。累计 c_2=Σx_i、c_5=Σy_i，并维护

$$ R=\prod r_i\pmod {10}. $$

每配对一个 2 和一个 5，就对应删去一个末尾 0，一共能配 min(c_2,c_5) 对。删零后的乘积最后一位便是

$$ R\times2^{c_2-\min(c_2,c_5)} \times5^{c_5-\min(c_2,c_5)}\pmod {10}. $$

两个剩余指数不可能同时为正。若剩余 2 的指数为 k>0，个位按 2,4,8,6 循环，周期为 4；若剩余 5，个位恒为 5。R 中的每个因子已不含 2、5，它们相乘时只需保留个位。初始 R=1,c_2=c_5=0 对应尚未乘入任何数的基础乘积 1。

所有被消掉的 2×5 都恰好对应一个末尾 0。剩下的因子仍保留在式子里，因此结果没有少乘任何部分。

设输入中 2、5 的总指数为 E，时间复杂度为 O(n+E)，而 a_i<=10^9 时 E<30n；空间复杂度为 O(1)。n<=10^6 时可通过。

代码

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int ans = 1;
    int c2 = 0;
    int c5 = 0;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        while (x % 2 == 0) {
            x /= 2;
            ++c2;
        }
        while (x % 5 == 0) {
            x /= 5;
            ++c5;
        }
        ans = ans * (x % 10) % 10;
    }

    int d2 = c2 - min(c2, c5);
    int d5 = c5 - min(c2, c5);

    if (d2 > 0) {
        const int pw2[4] = {6, 2, 4, 8};
        ans = ans * pw2[d2 % 4] % 10;
    }
    if (d5 > 0) {
        ans = ans * 5 % 10;
    }

    cout << ans << '\n';
    return 0;
}

实现核对

c2、c5 对应 c_2,c_5；ans 对应 R 乘上尚未配对的 2 或 5 后的个位；d2、d5 是删去 min(c_2,c_5) 对配后剩下的指数。