题目描述
游游拿到了一个数组，她准备在其中选择两个数，使得乘积的末尾至少有x个0。游游想知道，至少有多少种不同的取数方法？
输入描述:第一行输入两个正整数n和x，代表数组的大小以及乘积末尾0的数量。第二行输入n个正整数ai，代表游游拿到的数组。1≤n,x≤10^5,1≤ai≤10^9
输出描述:输出一个整数，代表游游选择的方案数。
#include <iostream> #include <vector> using namespace std; const int MAX_R = 40, MAX_C =20; int main() { vector<vector<int>> cnt(MAX_R, vector<int>(MAX_C)); int n, x; cin >> n >> x; for (int i = 0; i < n; ++i) { int ai; cin >> ai; int p2 = 0, p5 = 0; while (ai % 2 == 0) { p2++, ai /= 2; } while (ai % 5 == 0) { p5++, ai /= 5; } cnt[p2][p5]++; } long long ans = 0; for (int i = 0; i < MAX_R; ++i) { for (int j = 0; j < MAX_C; ++j) { for (int i2 = max(0, x - i); i2 < MAX_R; ++i2) { for (int j2 = max(0, x - j); j2 < MAX_C; ++j2) { ans += (i == i2 && j == j2 ? cnt[i][j] * (cnt[i][j] - 1LL) : cnt[i][j] * cnt[i2][j2]); } } } } cout << ans / 2 << endl; return 0; }
