文章目录
前言
前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是300+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！
- 目前是打算参加Java组，所以所有的题解都是Java。
本章节二分与前缀和的习题一览：包含所有题目的Java题解链接
例题：无链接的直接见当前博客
习题：
一、二分
整数二分
知识点
1、确定一个区间，目标值一定在这个区间中。
2、找一个性质，使得这个性质满足两点：①具有二段性【前半段满足，后半段不满足】。②答案是二段性的分界点。
实数二分不需要考虑这些问题：
核心模板知识点
二分查找算法模板：y总总结。
若是区间为[l, mid]，[mid + 1, r]
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
若是区间为[l, mid - 1]，[mid, r]
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid - 1;
else l = mid;
}
例题
示例题目：704. 二分查找
题目内容：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
题目解决：
[l, mid],[mid + 1, r]情况：
class Solution {
public boolean check(int mid, int target) {
if (mid < target) return true;
return false;
}
//-1,0,3,5,9,12
//check：如果nums[mid] < target，l = mid + 1 否则 r = mid => [l, mid],[mid + 1, r] => mid = (l + r) / 2
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + r >> 1;
if (check(nums[mid], target)) l = mid + 1;
else r = mid;
}
return target == nums[l] ? l : -1;
}
}[l, mid - 1],[mid, r]情况：
class Solution {
public boolean check(int mid, int target) {
if (target < mid) return true;
return false;
}
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(nums[mid], target)) r = mid - 1;
else l = mid;
}
return target == nums[l] ? l : -1;
}
}模板题：AcWing 789.数的范围
题目：Acwing 数的范围-二分算法-java实现
题目内容如下：
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例
输出样例
题解
package com.changlu.java;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int N = 100000;
private static int n, q, target;
private static int[] arr = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = cin.readLine().split(" ");
n = Integer.parseInt(s1[0]);
q = Integer.parseInt(s1[1]);
String[] s2 = cin.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(s2[i]);
}
while (q != 0) {
target = Integer.parseInt(cin.readLine());
//开始找左边
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] >= target) r = mid;
else l = mid + 1;
}
if (arr[l] != target){
System.out.printf("%d %d\n", -1, -1);
}else {
//确定最左边范围
int left = l;
l = 0;
r = n - 1;
//确认最右边范围
while (l < r) {
int mid = l + r + 1 >> 1;
if (arr[mid] <= target) l = mid;
else r = mid - 1;
}
int right = l;
System.out.printf("%d %d\n", left, right);
}
q--;
}
}
}
实数二分
知识点
模板题：AcWing 790.数的三次方根
题目链接：数的三次方根
代码模板：
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
题目内容：Acwing 数的范围-二分算法-java实现
数的三次方根
给定一个浮点数 n，求它的三次方根。
输入格式：共一行，包含一个浮点数 n。
输出格式：共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围：−10000≤n≤10000
输入样例：1000.00
输出样例：10.000000
题解
首先题目给出保留6位小数，所以这里精度为6位
import java.util.*;
import java.io.*;
class Main{
static double n;
public static void main(String[] args)throws Exception{
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
n = Double.valueOf(cin.readLine());
double l = -10000, r = 10000;
while (r - l > 1e-6) {
double mid = (l + r) / 2;
if (mid * mid * mid >= n) r = mid;
else l = mid;
}
System.out.printf("%.6f", l);
}
}
习题
题1：AcWing 730.机器人跳跃问题【中等】
来源：今日头条2019，笔试题
题目链接：730. 机器人跳跃问题
分析如下：
同样是采用二分来进行解决问题，比较核心的是在check函数中，我们对于mid >= 1e5情况时直接返回true，因为当满足该情况时，无需再进行往下递推去处理，因为一定是>0的。【若是不做该处理，可能会出现溢出出现负数的情况】
复杂度分析：时间复杂度O(nlogn)。计算一下：log(1e5)约等于30，接着30*1e5，此时就是300万，加上中间的一个剪枝处理，时间复杂度会进行优化。
import java.util.*;
import java.io.*;
class Main {
static int n;
static int[] h = new int[100010];
//结果集
static int res;
//返回false表示当前的初始的高度不够
public static boolean check(int mid) {
for (int i = 0; i < n; i++) {
mid = 2 * mid - h[i];
if (mid < 0) return false;
//若是mid>1e5，此时会不断的进行向上递增，因为若是下一次机器的高度就算是1e5，那么通过当前的mid两倍求得的结果依旧是>=1e5
if (mid >= 1e5) return true;
}
return true;
}
public static void main(String[] args) throws Exception{
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
n = Integer.valueOf(cin.readLine());
String[] s = cin.readLine().split(" ");
for (int i = 0; i < n; i++) {
h[i] = Integer.valueOf(s[i]);
}
//接着来开始进行处理计算
int l = 0, r = (int)1e5;
while (l < r) {
int mid = l + r >> 1;
//符合条件尝试继续往前推举
//[l, mid] [mid + 1, r]
if (check(mid)) r = mid;
else l = mid + 1;
}
System.out.printf("%d", l);
}
}
题2：AcWing 1221.四平方和【简单，蓝桥杯题】
题目链接：1221. 四平方和
题解链接：AcWing 1221. 四平方和（每日一题·春季）
标签：暴力、二分(枚举的最大数)、哈希
思路：首先会去想枚举3个数字来去暴力求解，但是发现运算的次数为十几亿，这个时间复杂度肯定会超时，那么我们将其优化为枚举两个数字，首先去枚举b、d并且使用数组来存储起来它们的和与相应的数组。
1、借助map
//500 0000 平方 2200
//暴力 2000^3 60 0000 0000
//暴力 2000^2 400 0000
import java.util.*;
import java.io.*;
class Main {
static class Pair<K, V>{
K c;
V d;
public Pair(K c, V d) {
this.c = c;
this.d = d;
}
}
private static int n;
//记录两个合并值以及相对应的pair
private static Map<Integer, Pair<Integer, Integer>> buckets = new HashMap<>();
//注意：此题是从小到排序，那么就需要先将c、d预存起来，之后重新去枚举a、b即可求解
public static void main(String[] args)throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
n = Integer.valueOf(cin.readLine());
for (int c = 0; c * c <= n; c++)
for (int d = c; d * d + c * c <= n; d++) {
int sum = c * c + d * d;
//若是存在直接输出
if (!buckets.containsKey(sum)) {
//若是不存在来进行存储
buckets.put(sum, new Pair<Integer, Integer>(c, d));
}
}
for (int a = 0; a * a <= n; a++)
for (int b = a; b * b + a * a <= n; b++) {
int coin = n - a * a - b * b;
if (buckets.containsKey(coin)) {
Pair<Integer, Integer> pair = buckets.get(coin);
System.out.printf("%d %d %d %d", a, b, pair.c, pair.d);
return;
}
}
}
}
2、数组来开辟空间（最优解）
//500 0000 平方 2200
//暴力 2000^3 60 0000 0000
//暴力 2000^2 400 0000
import java.util.*;
import java.io.*;
class Main {
private static int N = (int)5e6 + 10;
private static int n;
//1千万个空间
//各自存储相应的一个索引位置
private static int[] C = new int[N], D = new int[N];
//注意：此题是从小到排序，那么就需要先将c、d预存起来，之后重新去枚举a、b即可求解
public static void main(String[] args)throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
n = Integer.valueOf(cin.readLine());
//填充-1
Arrays.fill(C, -1);
Arrays.fill(D, -1);
//首先去枚举c、d
for (int c = 0; c * c <= n; c++)
for (int d = c; d * d + c * c <= n; d++) {
int sum = c * c + d * d;
//若是存在直接输出
if (C[sum] == -1) {
C[sum] = c;
D[sum] = d;
}
}
//最后去枚举a、b
for (int a = 0; a * a <= n; a++)
for (int b = a; b * b + a * a <= n; b++) {
int coin = n - a * a - b * b;
if (C[coin] != -1) {
System.out.printf("%d %d %d %d", a, b, C[coin], D[coin]);
return;
}
}
}
}
题3：AcWing 1227.分巧克力【简单，蓝桥杯题】
题目链接：1227. 分巧克力
分析：
一块巧克力（h[i]，k[i]）分割k.k大小的正方形小蛋糕，可以切得个数为：
由题目得知，蛋糕的块数最大为100000块，也就是10万，题目需要让我们求得能够切得满足k块的最大巧克力方形边长。
暴力枚举的话就是对边长1-100000的进行暴力枚举10万块，时间复杂度为100000 x 100000 = 1千亿，绝对会超时，那么我们需要去降低复杂度。
这里我们可以发现，随着边长的增加，相应的块数一定会减少，对于单调性递增或递减的情况我们可以使用二分来进行解决：
//mid指代当前切割蛋糕的数量，k指代题目要求的切割数量
//若是>=，表示还可能有更大的蛋糕边长可进行切割
若是mid >= k，l = mid
r = mid - 1
题解：
import java.util.*;
import java.io.*;
class Main {
private static int N = (int)1e5 + 10;
private static int n, k;
private static int[] H = new int[N], W = new int[N];
public static boolean check(int mid) {
//遍历所有的蛋糕来查看当前的mid是否满足>=k
int res = 0;
for (int i = 0; i < n; i++) {
res += (H[i] / mid) * (W[i] / mid);
//若是中途有>=k，那么就返回true
if (res >= k) return true;
}
return false;
}
public static void main(String[] args)throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
//读取初始值
String[] s = cin.readLine().split(" ");
n = Integer.valueOf(s[0]);
k = Integer.valueOf(s[1]);
int i = 0;
while (i < n) {
String[] s1 = cin.readLine().split(" ");
H[i] = Integer.valueOf(s1[0]);
W[i] = Integer.valueOf(s1[1]);
i++;
}
//定义左右边界（切割蛋糕的边长）
int l = 0, r = (int)1e5;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
System.out.printf("%d", l);
}
}
额外
leetcode：35. 搜索插入位置
class Solution {
//mid >= target r = mid
//else l = mid + 1
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
//System.out.printf("%d, %d, %d\n", mid, l, r);
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l + (target > nums[l] ? 1 : 0);
}
}二、前缀和
知识点
简述：快速计算某一个区间内的前缀和，暂时不能够支持修改操作。
例如让你计算指定[i,j]区间的和，正常的思路就是首先计算[0, i]之间的和，接着计算[0, j]之间的和，最后将后者的和减去前者的和即可求得。
那么求区间的和时间复杂度为O(n)。
结论：使用前缀和实际上就是用空间来去优化时间复杂度，原本O(n)复杂度去优化为O(1)的复杂度，但是若是进行了修改操作，那么求区间值就会失效。
应用场景：多层for来进行优化，空间换时间。
模板题
一维前缀和：AcWing 795.前缀和
题目链接：acwing795：前缀和
题目内容：
题目内容：输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。
输入格式：
第一行包含两个整数n和m。
第二行包含n个整数，表示整数数列。
接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。
输出格式:
共m行，每行输出一个询问的结果。
数据范围:
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入输出样例：
样例输入1：
5 3
2 1 3 6 4
1 2
1 3
2 4
样例输出1：
3
9
10
题解模板：
import java.util.*;
import java.io.*;
class Main {
private static final int N = 100010;
private static int n, m;
private static int []arr = new int[N];
private static int []sum = new int[N];
public static void main(String[] args)throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
String[] s = cin.readLine().split(" ");
n = Integer.valueOf(s[0]);
m = Integer.valueOf(s[1]);
s = cin.readLine().split(" ");
for (int i = 1; i <= n; i++) {
arr[i] = Integer.valueOf(s[i - 1]);
//数组保存前缀和
sum[i] = sum[i - 1] + arr[i];
}
while (m != 0) {
s = cin.readLine().split(" ");
//O(1)的时间复杂度计算区间值
System.out.printf("%d\n", sum[Integer.valueOf(s[1]) + 1] - sum[Integer.valueOf(s[0]) + 1]);
m--;
}
}
}
二维前缀和：AcWing 796.子矩阵的和
题目链接：acwing796：子矩阵的和
题目内容：
描述：输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式：
第一行包含三个整数n，m，q。
接下来n行，每行包含m个整数，表示整数矩阵。
接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。
输出格式：
共q行，每行输出一个询问的结果。
数据范围：
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21
分析：两个公式分别推导
题解模板：
import java.util.*;
import java.io.*;
class Main {
private static final int N = 1010;
private static int n, m, q;
private static int[][] arr = new int[N][N], sum = new int[N][N];
public static void main(String[] args)throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
String[] s = cin.readLine().split(" ");
n = Integer.valueOf(s[0]);
m = Integer.valueOf(s[1]);
q = Integer.valueOf(s[2]);
for (int i = 1; i <= n; i ++) {
s = cin.readLine().split(" ");
for (int j = 1; j <= m; j ++) {
arr[i][j] = Integer.valueOf(s[j - 1]);
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
}
}
while (q != 0) {
s = cin.readLine().split(" ");
int x1 = Integer.valueOf(s[0]);
int y1 = Integer.valueOf(s[1]);
int x2 = Integer.valueOf(s[2]);
int y2 = Integer.valueOf(s[3]);
System.out.printf("%d\n", sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
q--;
}
}
}
习题
题1：AcWing 99.激光炸弹【简单】
来源：《算法竞赛进阶指南》, HNOI2003
题目链接：99. 激光炸弹
标签：二维前缀和
分析：本道题实际上就是二维前缀和的一个应用。
根据给出的输入样例，我们来进行分析一下：
2 1
0 0 1
1 1 1
//N表示目标xy以及相应w的值（对应下面有n行） R表示爆照的正方形边长
N = 2 R = 1
x = 0 x = 0 w = 1
x = 1 y = 1 w = 1
对应输入案例的图如下：
接着读题，题目中说明了爆炸范围，即那个正方形的边必须和 x，y轴平行：
既然题目给我们确定的爆炸范围，也就是上图的第一个示例，那我们之后来计算二维前缀和时就有了确定的操作步骤。
注意点：
1、二维数组不能有两个，两个的话就会出现超限制内存的情况。
2、整个区域范围的长、宽一定要进行初始化，根据扫描的范围来设置初始值。
题解：
//R：正方形范围（炸弹范围）
//N：N个目标
//x,y表示坐标
//w：表示该坐标的的价值
//输入值对应内容
//2：目标数(N) 1：炸弹边长(R)
//对应的目标xy及价值
import java.util.*;
import java.io.*;
class Main {
private static final int N = 5010;
private static int n, r;
//最大空间：2500 0000 //两千五百万，若是设置两个数组的话，那么就会为五千万，此时即有可能超过指定内存空间168MB
//168MB => 4400万 【一个int 4个字节】
private static int[][] arr = new int[N][N];//二维前缀数组同样借助arr表示
public static void main (String[] args)throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
String[] s = cin.readLine().split(" ");
n = Integer.valueOf(s[0]);
//由于最大的x,y范围为5000，那么实际上地图最大就是5000（题目中若是>5000，那么则使用5000的范围进行扫描）
r = Math.min(5001, Integer.valueOf(s[1]));
//自定义长、宽（根据扫描的范围作为初始值）
int height = r, weight = r;
while (n != 0) {
s = cin.readLine().split(" ");
int x = Integer.valueOf(s[0]) + 1;
int y = Integer.valueOf(s[1]) + 1;
int w = Integer.valueOf(s[2]);
arr[x][y] += w;
height = Math.max(height, x);
weight = Math.max(weight, y);
n--;
}
//构造前缀数组
for (int i = 1; i <= height; i++)
for (int j = 1; j <= weight; j++)
arr[i][j] = arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1] + arr[i][j];
//来进行扫描，方形右下角(i, j)为准
int res = 0;
for (int i = r; i <= height; i++)
for (int j = r; j <= weight; j++)
res = Math.max(res, arr[i][j] - arr[i][j - r] - arr[i - r][j] + arr[i - r][j - r]);
System.out.printf("%d", res);
}
}
题2：AcWing 1230.k倍区间【蓝桥杯，中等】
题目链接：1230.k倍区间
分析：
暴力枚举O(n3) => 优化（前缀和省去一个for循环）O(n2) => 存余数O(n)
下面是依次推举过程：
暴力枚举：O(n3)，10万.10万.10万 1015，绝对超时
//枚举左右端点
int res = 0;
for (int r = 1; r <= n; r++) //右端点
for (int l = 1; l <= r; l++) { //左端点
int sum = 0;
for (int i = l; i <= r; i++) sum += arr[i];
if (sum % k == 0) res++;
}
优化（借助前缀和，可进行优化区间），优化为O(n2)，此时为1010，10000 0000 00，一百亿也超时
s[]//前缀区间
int res = 0;
//枚举左右端点
for (int r = 1; r <= n; r++) //右端点
for (int l = 1; l <= r; l++) { //左端点
int sum = s[r] - s[l];//借助前缀和快速求得区间
if (sum % k == 0) res++;
}
最终优化：时间复杂度O(n)，不超时
//我们拿到上面的一部分for循环
for (int l = 1; l <= r; l++) { //左端点
int sum = s[r] - s[l];//借助前缀和快速求得区间
if (sum % k == 0) res++;
}
//上述代码我们简化一下，实际上是表示从1-r中找到(s[r] - s[l]) % k == 0的情况
//(s[r] - s[l]) % k == 0 可进行拆分 s[r] % k - s[l] % k == 0，实际上就是表示s[r] % k == s[l] % k
for (int l = 1; l <= r; l++) { //左端点
if (s[r] % k == s[l] % k) res++;
}
//二次简化下：从1-r中找到s[r] % k == s[l] % k的个数，由于这个r是不断进行变化的，若是变为r+1，那么此前的r个（s[r] % k实际上是无需进行重复计算的）
//我们来进行举例，例如：1-r => 1-3，s[r] % k == s[l] % k
s[3] % k == s[1] % k
s[3] % k == s[2] % k
s[3] % k == s[3] % k
//若是此时r+1，那么为1-4
s[4] % k == s[1] % k
s[4] % k == s[2] % k
s[4] % k == s[3] % k
S[4] % K == S[4] % K
此时你可以看到后面的s[1]%k、s[2]%k、s[3]%k，此前是已经进行求得过了
//如何基于此来进行优化呢？我们可再次使用一个cnt数组来保存%运算的结果
int res = 0;
cnt[0] = 1;//简化cnt[(int)(sum[0] % k)]++;
for (int r = 1; r <= n; r++) {
res += cnt[s[r] % k];//获取1-(r-1)中与s[r] % k的结果匹配的个数，直接可类比for (int l = 1; l <= r; l++)
cnt[s[r] % k]++;//对当前s[r] % k的计数+1，为之后提供匹配遍历
}
//下方是举例子
s[1] = 1 % 2 = 1
s[2] = 3 % 2 = 1
s[3] = 6 % 2 = 0
s[4] = 10 % 2 = 0
s[5] = 15 % 2 = 1
1-1
1([1,1]) 1 0
1-2
3([1,2]) 2([2,2]) 1 2 1
1-3
6([1,3]) 5([2,3]) 3([3,3]) 1 2 3 1
1-4
10([1,4]) 9([2,4]) 7([3,4]) 4([4,4]) 1 2 3 4 2
1-5
15([1,5]) 14([2,5]) 12([3,5]) 9([4,5]) 5([5,5]) 1 2 3 4 5 2
题解：
import java.util.*;
import java.io.*;
class Main {
private static final int N = 100010;
private static int n, k;
private static long[] sum = new long[N];//注意前缀和相加可能会爆int
//保存临时%运算结果值得数量
private static long[] cnt = new long[N];
public static void main(String[] args)throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
String[] s = cin.readLine().split(" ");
n = Integer.valueOf(s[0]);
k = Integer.valueOf(s[1]);
//计算前缀和
for (int i = 1; i <= n; i++){
String numStr = cin.readLine();
sum[i] = Integer.valueOf(numStr) + sum[i - 1];
}
//计算k倍区间得个数
long res = 0;
cnt[0] = 1;//简化cnt[(int)(sum[0] % k)]++;
for (int r = 1; r <= n; r++) {
res += cnt[(int)(sum[r] % k)];
cnt[(int)(sum[r] % k)]++;
}
System.out.printf("%d", res);
}
}
