首页 > 试题广场 > 模数求和
[编程题]模数求和
  • 热度指数:8020 时间限制: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时可取得最大值。
# 假设 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)
这个题的重点在于要求的  f(m)  的值,然而我们总想求 m 的值,(#吐血) 
发表于 2019-12-28 14:09:20 回复(1)
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)
#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)
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)
其实 不用考虑这么多 ,是否存在一个数字 是所有数最小公倍数,同时题目没说这个数字范围。所以直接将最小公倍数作为m 进行计算就可以,不要陷入误区
发表于 2020-08-14 12:41:34 回复(0)
//数学理论
//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)
 //这道题的难点就在于找规律 根据例题可以看到 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)
// 找规律
#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)
#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)
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)
"""
规律题,总能找到一个数使得各余数为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)
余数最大,即每个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)
主要是求最小公倍数
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)
注意所求结果,不是要求出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)
思路:
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)
// 假设 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)
当 m 取最大值的时候,假设所有的取模都能取到  ai - 1,所以就有:
m = a1 * b1 + (a1 - 1) = a2 * b2 + (a2 - 1) = ai * bi + (ai - 1);  (i <= n)
则  ai * bi + (ai - 1) == aj * bj + (aj - 1)  (i != j ,且 i <= n)
ai * (bi  + 1) == aj * (bj  + 1)
所以一定可以找到满足条件的 bi ,所以取模都能取到  ai - 1
结论就是所有的输入减去 n 就是答案;
发表于 2020-07-08 11:46:35 回复(0)
n = int(input())
count = 0

s = input().split(" ")
for i in range(n):
    count += int(s[i])

print(count - n)

发表于 2020-06-17 10:27:41 回复(0)
首先看题目,是求出这个方程的最大值,也就是后面那些个括号里所有数取余都要最大值。我们知道,x%y最大值肯定是y-1,也就是x=y-1,所以,只要把输入的数加起来再减去一共多少数就出来了
Scanner sc=new Scanner(System.in);
        int n = Integer.parseInt( sc.nextLine() );
        int[] arr = new int[n];
        String[] strArr = sc.nextLine().split( " " );

        int sum = 0;
        for( int i=0; i<n; i++ ) {
            sum += Integer.parseInt( strArr[i] );
        }

        System.out.println( sum-n );

发表于 2020-06-14 20:26:33 回复(0)