当前位置: 代码迷 >> 综合 >> 模数求和C++实现
  详细解决方案

模数求和C++实现

热度:87   发布时间:2024-01-30 13:04:03.0

现给定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=11带入,11%3=2,11%4=3,11%6=5,规律就是m为这三个数的最小公倍数-1,才能对每个数获得最大的余数,f(m)才能是最大的,那么每个数最大的余数为其本身减1,f(m)=(3-1)+(4-1)+(6-1)=10,妙不妙,就不用求最小公倍数了。

代码

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

 

  相关解决方案