两数之和被k整除的方案数

[编程题]两数之和被k整除的方案数

热度指数：39 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 $n$ 个元素组成的数组，和一个正整数 $k$ 。求取两个数之和能被 $k$ 整除的方案数（即两数之和为k的倍数的方案数）

输入描述:

第一行输入两个正整数  和  。
第二行输入  个数  ，用空格隔开。表示整个数组。

输出描述:

一个正整数，代表方案的数量。

示例1

输入

7 4
1 2 3 3 4 2 4

输出

说明

取下标<1,3>，1+3=4是4的倍数。
取下标<1,4>，1+3=4是4的倍数。
取下标<2,6>，2+2=4是4的倍数。
取下标<5,7>，4+4=8是4的倍数。

算法知识视频讲解

Java

重剑无锋zcy

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s1=sc.nextLine();
        String[] ss1=s1.split("\\s");
        int n=Integer.parseInt(ss1[0]);
        int k=Integer.parseInt(ss1[1]);
        String s2=sc.nextLine();
        String[] ss2=s2.split("\\s");
        long [] tong=new long[k];    // 桶里面元素可能大于Int的最大值
        long re=0;                   // 返回值可能大于Int的最大值
        for(int i=0;i<n;i++){
            tong[Integer.parseInt(ss2[i])%k]++;
        }
        for(int i=1;i<k/2;i++){
            re+=tong[i]*tong[k-i];
        }
        //处理余数为0；Cn2
        re+=tong[0]*(tong[0]-1)/2;
        // 偶数时，需要考虑2+2=4
        if(k%2==0){
            re+=tong[k/2]*(tong[k/2]-1)/2;
        }
        System.out.println(re);
    }
}

考察桶排序的基础

发表于 2021-03-29 22:25:14 回复(0)