模数求和

[编程题]模数求和

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

现给定n个整数，并定义一个非负整数m，且令f(m) = (m%a₁)+(m%a₂)+...+(m%a_n)。
此处的X % Y的结果为X除以Y的余数。
现请你找出一个m，求出f(m)的最大值。

输入描述:

输入包含两行，第一行为一正整数n，(1<n<=3000)
第二行为n个整数a₁,a₂,...,a_n ，其中(2<=a_i<=10^5)

输出描述:

输出仅包含一行，输出f(m)的最大值

示例1

输入

3
3 4 6

输出

说明

就样例而言，当m取11时可取得最大值。

算法知识视频讲解

Java

何止hz

m的值有无数个，就是a1,a2,……,an的公倍数-1。

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

/**
 * @Author: coderjjp
 * @Date: 2020-05-09 17:54
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int ans = 0;
        String[] line2 = br.readLine().split(" ");
        for (int i = 0; i < n; i++)
            ans += Integer.valueOf(line2[i]);
        System.out.println(ans - n);
    }
}

发表于 2020-05-09 18:07:44 回复(0)

Java

咽喉上的刀

Java解答：找规律，尽量保证最大余数之和，即sum-n。

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a = new int[n];
        int sum = 0;
        for (int i=0;i<n;i++) {
            a[i] = input.nextInt();
            sum = sum + a[i];
        }
        System.out.println(sum-n);
    }
}

发表于 2019-08-02 20:04:01 回复(0)