携程笔试

100/100/15/100

第三题求一下解答，顺便贴一下第四题较笨的解法（就是暴力双重循环优化了下，分组二分）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, x;
    cin >> n >> x;
    map<int, vector<int>> cnt;
    long long ret = 0;
    for (int i = 0; i < n; ++i)
    {
        int num;
        cin >> num;
        int cnt5 = 0, cnt2 = 0;
        while (num % 5 == 0)
        {
            num /= 5;
            cnt5++;
        }
        while (num % 2 == 0)
        {
            num /= 2;
            cnt2++;
        }
        cnt[cnt5].push_back(cnt2);
    }
    for (int i = 0; i < cnt.size(); ++i)
        sort(cnt[i].begin(), cnt[i].end());

    for (int k = 0; k <= 12; ++k)
    {
        for (int i = 0; i < cnt[k].size(); ++i)
        {
            int pivot = cnt[k][i];
            for (int k2 = k; k2 <= 12; ++k2)
            {
                if (cnt[k2].size() == 0 || k2 + k < x)
                    continue;
                int pos = lower_bound(cnt[k2].begin(), cnt[k2].end(), x - pivot) - cnt[k2].begin();
                if (k2 == k)
                    ret += cnt[k2].size() - max(pos, i + 1);
                else
                    ret += cnt[k2].size() - pos;
            }
        }
    }
    cout << ret << endl;
    return 0;
}