首页 > 试题广场 >

模数求和

[编程题]模数求和

热度指数：8671 时间限制：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时可取得最大值。

算法知识视频讲解

Python

雷凌云

# 假设 m % x = x-1（x-1是能取到的最大余数，也就是说 m+1 是 x 的倍数）
# 如果 m+1 是所有数的倍数，则 f(m) 可以取到最大值，m+1 的值就是所有数的最小公倍数
# f(m) = (a1-1) + (a2-1) + ... + (an-1) = sum(a)-n
n = int(input())
a = list(map(int, input().split(' ')))
print(sum(a) - n)

编辑于 2019-09-10 12:48:23 回复(15)

offer怎么这么难

这个题的重点在于要求的 f(m) 的值，然而我们总想求 m 的值，（#吐血）

发表于 2019-12-28 14:09:20 回复(1)

Python

卷积神经网络哦

Python两行足矣

看完题目就可以有一个大胆的猜想，最大值不就是每个a作为除数能够得到的最大值减去1么

也即(a1 - 1) + (a2 - 1) + ... + (an - 1)

但是心里就想了这样的m真的存在么？真的有这样一个理想的m对所有的a取余的结果都是理论最大a-1么

证明一下即可对于样例所，方程如下，其中k1,k2,k3为正整数

3 * k1 + 2 = m

4 * k2 + 3 = m

6 * k3 + 5 = m

这里有3个独立方程，有4个未知数，未知数的个数大于方程的数目，必然有解。所以一定存在一个这样的m使得m对所有a取余的结果都是a-1

_, arr = input(), [int(x) - 1 for x in input().strip().split(' ')]
print(sum(arr))

发表于 2019-12-03 11:00:32 回复(6)

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)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n,sum=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum=sum+a[i]-1;
    }
    cout<<sum<<endl;
    return 0;
}

发表于 2019-07-12 22:51:33 回复(0)

pein531

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

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().trim());
        String[] strArr = br.readLine().trim().split(" ");
        // m%ai的最大值就是ai-1，如果m+1为所有ai的最小公倍数，就可以使得所有的ai被m+1整除，m能使m%ai=ai-1对任意i都成立
        int maxValue = 0;
        for(int i = 0; i < n; i++)
            maxValue += Integer.parseInt(strArr[i]) - 1;
        System.out.println(maxValue);
    }
}

发表于 2021-01-30 23:09:20 回复(0)

Decisivem

其实不用考虑这么多，是否存在一个数字是所有数最小公倍数，同时题目没说这个数字范围。所以直接将最小公倍数作为m 进行计算就可以，不要陷入误区

发表于 2020-08-14 12:41:34 回复(0)

C/C++

敲多码代

//数学理论
//1.n个数的最小公倍数 设为q
//2.令m=q-1,则m%a=a-1;
//3.sum=a1-1+a2-1+a3-1……=a1+a2……+an-n
#include <iostream>
using namespace std;
int main()
{
    int n,a;
    cin>>n;
    int res=0;
    while(cin>>a)
        res+=a;
    cout<<res-n<<endl;
    return 0;
}

发表于 2020-05-22 12:14:51 回复(0)

dragonlogin

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

int main() {
    int n = 0;
    cin >> n;
    int sum = 0;
    int x = 0;
    for (int i=0; i<n; ++i) {
        cin >> x;
        sum += x;
    }
    cout << sum - n <<endl;
    return 0;
}

发表于 2019-10-19 13:55:42 回复(0)

C/C++

nbgao

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

int main(){
    int n;
    cin>>n;
    int x, s=0;
    for(int i=0;i<n;i++){
        cin>>x;
        s += x;
    }
    cout<<s-n<<endl;

    return 0;
}

发表于 2019-08-21 13:32:43 回复(0)

ElonB

"""
规律题，总能找到一个数使得各余数为ai-1。
"""

if __name__ == "__main__":
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    print(sum(a) - n)

发表于 2019-07-29 23:40:52 回复(0)

夏花爱秋叶

 //这道题的难点就在于找规律 根据例题可以看到 3 4 6分别对11的模式 2 3 5
// 也就是自身-1 ；然后我还试了一下，发现可以找这三个数的公倍数 也就是12 发现12的时候都是0,13的时候都是1！！！
// 所以在12-1 ，11的时候为最大，也就是自身-1.也就得出 最大值=总数-个数  也就是3+4+6-3=10
var n=parseInt(readline());
var arr=readline().split(' ').map(Number);
print(arr.reduce((a,b)=> a+b)-n);

发表于 2020-03-04 00:16:36 回复(0)

Java

牛客499848474号

import java.util.Scanner;

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

发表于 2024-11-02 19:42:06 回复(0)

Python3

TS9527

很数学的一道题

对于每一项而言，我们希望取到最大，也就是说让 $m \mod a_i = a_i - 1$ 。可以构造m为a1, ..., a_i的最小公倍数减1，这样各项就是最大的。此时有 $f(m) = a_1 - 1 + a_2 - 1 + ... + a_n - 1 = \Sigma_{i = 1}^{n}a_i - n$

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        nums = list(map(int, filter(lambda x: len(x) > 0, input().split(' '))))
        # Get the result
        print(sum(nums) - n)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-09-02 14:18:46 回复(0)

TypeScript

矜持的微笑

const readline = require('readline');

const rl = readline.createInterface({

input: process.stdin,

output: process.stdout

});

let count = 0; //我们使用 count 变量来记录输入次数

rl.on('line', function (line) {

count++

let res=0

if(count===2){ //第二次输入时

let arr=line.split(' ')

res=arr.reduce((x,y)=>x*1+y*1,0)

console.log(res-arr.length)

}

});

编辑于 2024-01-04 22:35:59 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var n int
    fmt.Scan(&n)
    //思路，答案为所有数的最小公倍数减一后分别取余各个数的加和
    var x,sum int
    for n>0{
        fmt.Fscan(in,&x)
        sum+=x-1
        n--
    }
    fmt.Print(sum)
}

发表于 2023-03-17 23:12:24 回复(0)

Python 3

王学成_a

import sys

if __name__ == "__main__":
while True:
a = sys.stdin.readline().strip()
if not a :
break
b = sys.stdin.readline().strip().split()
b = [int(i) for i in b]
print(sum(b)-int(a))

发表于 2021-08-22 14:19:41 回复(0)

C/C++

牛客66829号

余数最大，即每个a[i]都余下a[i]-1,就是一个简单的求和

#include <iostream>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    long int a[3000];
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i]-1;
    }
    cout<<sum<<endl;
    return 0;
}

发表于 2020-08-07 01:12:32 回复(0)

牛客434949461号

主要是求最小公倍数

python3 求解：

import sys
def max_val(list1):
    ret = 1
    m = max(list1)
    n = len(list1)
    lt = []
    for i in range(n):
        for j in (1,m+1):
            if list1[i]%j==0 and j not in lt:
                lt.append(j)
    max_mul = max(lt)
    for a in list1:
        ret = ret*a
    ret = (ret//max_mul)-1
    return ret

if __name__ =="__main__":
    list0 = []
    list_new = []
    for line in sys.stdin:
        list_new = line.split()
        list_new = list(map(int,list_new))
        list0.append(list_new)
    n = list0[0][0]
    b = max_val(list0[1])
    sum_m = 0
    for i in range(n):
        sum_m = sum_m + b%list0[1][i]
    print(sum_m)

发表于 2020-07-31 12:10:05 回复(0)

C/C++

秋山红月

注意所求结果,不是要求出m,只是求最大的f(m)——即所有数的最大余数和。仔细想一想,每个正整数an的最大余数就是an-1，所以，f（m)的最大值即数列中每一个an-1的和。

求这个和就简单了：f(m)=a1+a2+...+...an-n。

如果要求m，就是求a1至an的整个数列的最小公倍数x，m=x-1 为所求。

要求a1至an的最小公倍数，可以求a1,a2的最小公倍数b2,再求b2,a3的最小公倍数b3，再求b3,a4...以至类推，最后的bn为这个数列的最小公倍数。bn-1就是m。

#include <iostream>
using namespace std;
int main(){
    int n,t;
    int i;
    int f=0;
    cin>>n;
    for(i=0;i<n;++i){
        cin>>t;      
        f+=t;
    }  
    cout<<f-n;
}

编辑于 2020-07-16 22:48:23 回复(0)