模数求和

[编程题]模数求和

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

算法知识视频讲解

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)