模数求和

[编程题]模数求和

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

算法知识视频讲解

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)

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)