首页 > 试题广场 >

K 的倍数

[编程题]K 的倍数

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

序列中任意个连续的元素组成的子序列称为该序列的子串。

现在给你一个序列 P 和一个整数 K ，询问元素和是 K 的倍数的子串的最大长度。

比如序列 [1,2,3,4,5]，给定的整数 K 为 5，其中满足条件的子串为 {5}、{2,3}、{1,2,3,4}、{1,2,3,4,5} ，

那么答案就为 5，因为最长的子串为 {1,2,3,4,5} ; 如果满足条件的子串不存在，就输出 0。

数据范围： $1 \le n \le 10^5 \$ ， $0 \le p_i \le 10^5 \$ ， $1 \le K \le 10^5 \$

输入描述:

第一行包含一个整数N, 1 ≤ 𝑁 ≤ 10⁵。

第二行包含 N 个整数𝑝𝑖，𝑝𝑖表示序列P第i个元素的值。0 ≤ 𝑝𝑖 ≤ 10⁵。第三行包含一个整数K，1 ≤ 𝐾 ≤ 10⁵。

输出描述:

输出一个整数ANS，表示答案。

示例1

输入

5
1 2 3 4 5
5

输出

示例2

输入

6
3 1 2 7 7 7
4

输出

算法知识视频讲解

向宇回桌

哇！一个类型转换，让我交了快20几次，ac率直接拉低10%...

import java.util.*;
public class Main {
    private static int MAX = (int) 10e5+5;
    private static int INT_MAX = 0x3f3f3f3f;
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] preSumIndexMin = new int[MAX]; Arrays.fill(preSumIndexMin, INT_MAX);
        int[] preSumIndexMax = new int[MAX]; Arrays.fill(preSumIndexMax, -INT_MAX);
        long[] preSum = new long[MAX];
        for (int i=1; i<=n; i++) {
            preSum[i] += sc.nextLong() + preSum[i-1];
        }
        int k = sc.nextInt();
        long ans = 0;
        for (int i=0; i<=n; i++) {
            int mod = (int)(preSum[i] % k);
            preSumIndexMin[mod] = Math.min(preSumIndexMin[mod], i);
            preSumIndexMax[mod] = Math.max(preSumIndexMax[mod], i);
            ans = Math.max(preSumIndexMax[mod] - preSumIndexMin[mod], ans);
        }
        System.out.println(ans);
        return;
    }
}

再附上一个CPP的。

#include <bits/stdc++.h>
const int MAX = 1e5+5;
using namespace std;
static int max_index[MAX];
static int min_index[MAX];
static long long presum[MAX];
int main(){
    int n; scanf("%d", &n);
    memset(presum, 0, sizeof(presum));
    for (int i=1; i<=n; i++) {
        scanf("%d", &presum[i]);
        presum[i] += presum[i-1];
    }
    int k; scanf("%d", &k);
    for(int i=0; i<MAX; i++) {max_index[i] = -0x3f3f3f3f;}
    for(int i=0; i<MAX; i++) {min_index[i] = 0x3f3f3f3f;}
    int ans = 0;
    for (int i=0; i<=n; i++) {
        int mod = (int)(presum[i] % k);
        min_index[mod] = min(min_index[mod], i);
        max_index[mod] = max(max_index[mod], i);
        ans = max(max_index[mod]-min_index[mod], ans);
    }
    printf("%d", ans);
    return 0;
}

编辑于 2019-02-11 00:31:14 回复(1)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] p = new int[n];
        String[] strs = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(strs[i]);
        }
        int k = Integer.parseInt(br.readLine());

        //sum[i + 1]: 序列p[0]...p[i]的和
        long[] sum = new long[n + 1];
        for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + p[i];

        int res = 0;
        for (int i = n; i >= 1; i--) {
            for (int j = 0; j < i; j++) {
                if ((sum[i] - sum[j]) % k == 0) {
                    res = Math.max(res, i - j);
                    break;
                }
            }
            if (res >= i - 1) break;
        }
        System.out.println(res);
    }
}

发表于 2019-01-13 20:51:45 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k, Max=0;
    scanf("%d", &n);
    long a[n+1]={0};
    for(int i=1;i<=n;i++){
        scanf("%ld", &a[i]);
        a[i] += a[i-1];
    }
    scanf("%d", &k);
    for(int i=1;i<=n;i++)
        for(int j=i+Max;j<=n;j++)
            if((a[j]-a[i-1])%k == 0)
                Max = max(Max, j-i+1);
    printf("%d\n", Max);
    return 0;
}

发表于 2020-09-11 13:18:26 回复(0)

幽蘭の戀

核心思想：

将之前输入得到的序列第i位变成包括他的前i位的和，构建一个序列用于存储第一次出现某个余数对应的序号i，当之后再出现相同余数，则之间的序列和能被k整除（对于余数为0的情况，只要出现整除情况就表示整个序列能被k整除）


	N =int(input());



	pi =[int(i) fori ininput().split()];



	pi =[0]+pi;



	k =int(input());



	mod =[-1]*k;



	mod[0] =0;



	ANS =0;



	fori inrange(1,len(pi)):



	    pi[i] =pi[i]+pi[i-1];



	    M =pi[i]%k;



	    ifmod[M] !=-1:



	        ANS =max(ANS, (i-mod[M]));



	    else:



	        mod[M] =i;



	print(ANS);

发表于 2019-04-08 10:42:49 回复(0)

想回家的海螺在拧螺丝

#include <bits/stdc++.h>
using namespace std;

int main() {
    int P; cin >> P;

    vector<long> preSum(P+1);
    for(int i = 1; i <= P; i++) {
        cin >> preSum[i];
        preSum[i] += preSum[i-1];
    }

    int k; cin >> k;

    vector<int> min_idx(k, 1e5+5), max_idx(k, -1e5-5); 
    
    int ans = 0;
    for(int i = 0; i <= P; i++) {
        int mod = preSum[i] % k;
        min_idx[mod] = min(min_idx[mod], i);
        max_idx[mod] = max(min_idx[mod], i);

        ans = max(ans, max_idx[mod]-min_idx[mod]);
    }

    cout<<ans;

    return 0;
}

发表于 2023-05-06 13:28:16 回复(0)

嘟嘟6668

///求和时要用long类型否则会超范围，也可以直接%k
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=Integer.valueOf(scan.nextLine());
            String[] strs=scan.nextLine().split(" ");
            n=strs.length;
            int[]data=new int[n];
            for(int i=0;i<n;i++)
                data[i]=Integer.valueOf(strs[i]);
            int k=Integer.valueOf(scan.nextLine());
            get(n,data,k);
        }

    }
    public static void get(int n,int[] data,int k){
        int[]mod=new int[k];
        long count=0;
        int ans=0;
        for(int i=0;i<k;i++)
            mod[i]=-1;
        for(int i=0;i<n;i++){
            count=count+data[i];
            int tem=(int)(count%k);

            if(tem==0){
                ans=Math.max(ans,i+1);
            }else{
                if(mod[tem]==-1){
                    mod[tem]=i;
                }else{
                    ans=Math.max(ans,i-mod[tem]);
                }
            }
        }
        System.out.println(ans);
    }
}

发表于 2019-05-12 15:48:42 回复(0)

hzpzlz1314

#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
int main(){
    int n,x;
    while(cin>>n){
        vector<long long int>dp(n+1);
        for(int i=1;i<=n;i++){
            cin>>dp[i];
            dp[i] = dp[i]+dp[i-1];
        }
        cin>>x;
        if(dp[n]%x==0){
            cout<<n<<endl;
            return 0;
        }
        int length = dp.size();
        int maxlen=-1;
        for(int len=length-1;len>=1;len--){
            bool is_he = false;
            for(int i=len;i<length;i+=1){
                long long int sum = dp[i]-dp[i-len];
                if(sum%x==0){
                    is_he=true;
                }
            }
            if(is_he){
                cout<<len<<endl;
                break;
            }
        }
    }
    return 0;
}

发表于 2019-04-20 16:42:52 回复(1)

Stubb

import java.util.*;
public class Main{

public static void main(String[]args){
Scanner in=new Scanner(System.in);
int a=in.nextInt();
int arr[]=new int[a];
for (int i = 0; i < arr.length; i++) {
            arr[i]=in.nextInt();
        }
int l=in.nextInt();
int max=0;
long sum=0;
for (int i = 0; i < arr.length; i++) {
            if(max>=arr.length-i+1) break;
sum=arr[i];
    for (int j = i+1; j < arr.length; j++) {

                sum+=arr[j];
                if (sum%l==0) {
                    max=Math.max(max, j-i+1);
                }
            }
        }
System.out.println(max);
}

}

发表于 2019-03-27 21:51:14 回复(1)

hts1

超过限制

n =int(input())
x = [int(i) for i in input().split(" ")]
k = int(input())
presum=[0]
ans = 0
for i in range(1,n+1):
    presum.append(presum[-1]+x[i-1])

max_index=[-10000 for i in range(max(presum))]
min_index=[10000 for i in range(max(presum))]

for i in range(0,len(presum)):
    mod = int(presum[i]%k)
    max_index[mod]=max(i,max_index[mod])
    min_index[mod]=min(i,min_index[mod])
    ans = max(ans,max_index[mod]-min_index[mod])
print(ans)

发表于 2019-03-24 10:32:25 回复(0)