首页 > 试题广场 > 多多的求和计算
[编程题]多多的求和计算
  • 热度指数:2283 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
多多路上从左到右有N棵树(编号1~N),其中第i个颗树有和谐值Ai。
多多鸡认为,如果一段连续的树,它们的和谐值之和可以被M整除,那么这个区间整体看起来就是和谐的。
现在多多鸡想请你帮忙计算一下,满足和谐条件的区间的数量。

输入描述:
第一行,有2个整数N和M,表示树的数量以及计算和谐值的参数。
( 1 <= N <= 100,000, 1 <= M <= 100  )
第二行,有N个整数Ai, 分别表示第i个颗树的和谐值。
( 0 <= Ai <= 1,000,000,000 )


输出描述:
共1行,每行1个整数,表示满足整体是和谐的区间的数量。
示例1

输入

5 2
1 2 3 4 5

输出

6

说明

长度为1: [2], [4]
长度为2: 无
长度为3: [1,2,3], [3,4,5]
长度为4: [1,2,3,4], [2,3,4,5]
长度为5: 无
共6个区间的和谐值之和可以被2整除。

备注:
对于50%的数据,有N<=1,000
对于100%的数据,有N<=100,000
#include <iostream>
#include <cstring>
using namespace std;
int main(){
    int n, m;
    cin>>n>>m;
    int arr[n];
    for (int i = 0; i < n; ++i){
        cin>>arr[i];
    }
    int map[m];//下标表示前缀和 % m后的值,map[i]表示取余后值为i的个数;
    memset(map, 0, sizeof(map));
    map[0] = 1;//需要设置这个初始值,看下面代码就懂了
    long sum = 0;
    long ans = 0;
    for (int i = 0; i < n; ++i){
        sum += arr[i];
        int index = sum % m;
        ans += map[index]++;
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2021-05-12 16:38:57 回复(6)
import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[] A = new int[N];
        for(int i = 0; i < N; i++){
            A[i] = scanner.nextInt();
        }
        int count = 0;
        int sum = 0;
        Map<Integer, Integer> record = new HashMap<>();
        //遍历数组nums之前,record提前放入 0:1 键值对,代表求第 0 项前缀和之前,前缀和 mod K 等于 0 这种情况出现了 1 次。
        record.put(0,1);
        for(int elem : A){
            sum+=elem;//前缀和
            int model = (sum % M + M) % M;//取余数
            //getOrDefault() 方法获取指定 key 对应对 value,如果找不到 key ,则返回设置的默认值0。
            record.put(model, record.getOrDefault(model, 0)+1);
        }
        //values() 方法返回映射中所有 value 组成的 Set 视图
        for(int n : record.values()){
            count+=n*(n-1)/2;
        }
        //for(Map.Entry<Integer, Integer> entry : record.entrySet()){
        //    count+=entry.getValue()*(entry.getValue()-1)/2;
        //}
        System.out.println(count);
    }
}

发表于 2021-05-21 22:18:05 回复(0)
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.stream.DoubleStream;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //哈希表+前缀和的知识点就可以解决90%了,但是注意,他给的数据很大,所以还要进一步处理~~
        int N = scanner.nextInt();
        int flag = scanner.nextInt();
        int[] num1 = new int[N];
        for (int i = 0; i < N ; i++) {
            num1[i] = scanner.nextInt();
        }
        int[] num2 = new int[N];
        num2[0] = num1[0]%flag;
        for (int i = 1; i < N ; i++) {
            num2[i] = (num1[i]+num2[i-1]) % flag;
        }

        HashMap<Integer, Integer> iMap = new HashMap<>();
        iMap.put(0,1);
        int sum = 0;
        long count = 0;

        for (int i = 0; i < N; i++) {
            if (iMap.containsKey(num2[i])) count += iMap.get(num2[i]);
            iMap.put(num2[i], iMap.getOrDefault(num2[i], 0) + 1);
        }

        System.out.println(count);
    }
}

发表于 2021-07-01 16:34:33 回复(0)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,m,a,sum=0,v[1005],ans;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n>>m;
    v[0]=1;/**< 用v数组统计每个位置前缀和余数的个数,相同余数的区间必然能被m整除 */
    for(i=1;i<=n;i++)
    {
        cin>>a;
        sum=(sum+a)%m;
        v[sum]++;
    }
    for(i=0;i<m;i++)/**< 相同余数任选2个都可以和谐区间 */
        ans+=v[i]*(v[i]-1)/2;
    cout<<ans;
    return 0;
}


发表于 2021-06-27 10:18:50 回复(0)
import java.util.*;

/**
 * @author xq
 * @create 2021-05-20-15:13
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
            A[i] = A[i] % M;
        }
        int[] sum = new int[N];
        sum[0] = A[0] % M;
        for (int i = 1; i < N; i++) {
            sum[i] = (sum[i - 1] + A[i]) % M;
        }
        long count = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        for (int i = 0; i < N; i++) {
            if (hashMap.containsKey(sum[i])) count += hashMap.get(sum[i]);
            hashMap.put(sum[i], hashMap.getOrDefault(sum[i], 0) + 1);
        }
        System.out.println(count);
    }
}
前缀和还是很简单的
发表于 2021-06-06 21:32:51 回复(1)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(f(arr,m));
    }
    public static long f(int[] arr,int m){
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int sum = 0;
        long res = 0;
        for(int i = 0; i< arr.length; i++){
            sum += arr[i] % m ;
            //余数
            int k = ((sum % m) + m)% m;
            if(map.containsKey(k)){
                res += map.get(k);
                map.put(k,map.get(k)+1);
            }else{
                map.put(k,1);
            }
        }
        return res;
    }
}
与LeetCode974思路一致,主要是int会越界,结果使用long,求前缀和时先取余 避免越界就AC了
发表于 2021-06-01 22:39:10 回复(0)
  • JavaScript 版本
    function sum(num, param, arr) {
      let total = 0
      for (let i = 1; i <= num; i++) {
          for (let j = 0; j <= num-i; j++) {
              let temporaryArr = arr.slice(j, j+i)
              if (eval(temporaryArr.join('+')) % param === 0) total++
          }
      }
      return total
    }
发表于 2021-05-20 16:57:33 回复(0)
presum[j]%m=presum[i]%m
发表于 2021-05-17 15:32:46 回复(0)
与力扣974题相同,对于连续的子数组,往往采用前缀和的方式解决。
发表于 2021-05-13 16:32:34 回复(0)
n,m = list(map(int, input().strip().split(' ')))
ai=list(map(int,input().strip().split(' ')))
li={}
sum=0 for i in ai:
    sum+=i
    yu=sum%m if yu not in li.keys():
        li[yu]=1  else:
        li[yu]+=1 hh=0 for i,j in li.items(): if i==0:
        hh+=j
    nn=j*(j-1)//2  hh+=nn print(hh)
发表于 2021-05-11 00:02:47 回复(0)