首页 > 试题广场 >

模数求和

[编程题]模数求和
  • 热度指数：8627 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现给定n个整数，并定义一个非负整数m，且令f(m) = (m%a1)+(m%a2)+...+(m%an)。
此处的X % Y的结果为X除以Y的余数。
现请你找出一个m，求出f(m)的最大值。


输入描述:
输入包含两行，第一行为一正整数n，(1<n<=3000)
第二行为n个整数a1,a2,...,an ，其中(2<=ai<=10^5)


输出描述:
输出仅包含一行，输出f(m)的最大值
示例1

输入

3
3 4 6

输出

10

说明

就样例而言，当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怎么这么难头像 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头像 无心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头像 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头像 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头像 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头像 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头像 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)
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)
Go
小谷围做题家头像 小谷围做题家 
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头像 王学成_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号头像 牛客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号头像 牛客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)
牛客895377832号头像 牛客895377832号
思路：
a1可以取得的最大模数等于a1-1; (x1*a1+a1-1)=a1(x1+1)-1=m=a1*x1'-1=> m-1=a1*x1'，
a2可以取得的最大模数等于a2-1;`(x2*a1+a1-1)=a2(x2+1)-1=m=a2*x2'-1=> m-1=a2*x2'，
所以m-1是a1,a2的公倍数，存在m

所以最大就是a1+a2+a3-n
发表于 2020-07-14 17:44:14 回复(0)
C/C++
zxc君陌头像 zxc君陌
// 假设 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
int main()
{
    int n = 0;
    int NumArr = 0 ;
    unsigned int Sum = 0;
    int i = 0;
    
    scanf("%d",&n);
    n = n > 3000 ? 3000:((n < 2)?2:n);

    for(; i < n; i++)
    {
        scanf("%d",&NumArr);
        NumArr = NumArr > 100000 ? 100000:((NumArr < 2)?2:NumArr);
        
        Sum += NumArr - 1;
    }
    printf("%d\n",Sum);
    
    return 0;
}
发表于 2020-07-09 17:47:42 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 网易 2019 基础数学 拼多多 数学 Java工程师
上传者：小小
难度：
41条回答 8605浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号