腾讯音乐9月26日笔试

import java.util.*;


public class code2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型ArrayList
     * @param x int整型
     * @return int整型
     */
    public int get_mod_2(int x) {
        int res = 0;
        while (x%2==0) {
            res++;
            x /= 2;
        }
        return res;
    }

    public int get_mod_5(int x) {
        int res = 0;
        while (x%5==0) {
            res++;
            x /= 5;
        }
        return res;
    }
    public int getSubarrayNum (ArrayList<Integer> a, int x) {
        // write code here
        long[][] cnt_arr = new long[2][a.size()]; // 记录因子有多少2 因子有多少5
        for (int i = 0; i < a.size(); i++) {
            cnt_arr[0][i] = get_mod_2(a.get(i));
            cnt_arr[1][i] = get_mod_5(a.get(i));
        }

        int[] records = new int[a.size()];  // 以下标开始，存的数是区间的终止位置，区间内的数相乘结尾至少有x个0，且保证区间最短
        for (int i = 0; i < a.size(); i++) {
            records[i] = -1;
        }
        long record_2 = 0;
        long record_5 = 0;
        int begin_index = 0;
        for (int end_index = 0; end_index < a.size(); end_index++) {
            record_2 += cnt_arr[0][end_index];
            record_5 += cnt_arr[1][end_index];
            while (record_2 >= x && record_5>=x) {
                records[begin_index] = end_index;
                record_2 -= cnt_arr[0][begin_index];
                record_5 -= cnt_arr[1][begin_index];
                begin_index++;
            }
        }


        int res = 0;    
        for (int i = 0; i < records.length; i++) {
            if (records[i] == -1) break;    // 当前位置为-1，表示后面区间所有的数相乘都不能得到末尾有两个0的数
            res += ((a.size()-records[i]) % ((int)(Math.pow(10,9)+7))); // 当前位置开头的结果
        }

        return res;
   }

}