前言

写写题

题目相关

link

题目大意

给你$n$个正整数aia_iai​
f(x)=∑i=1n(ai%x+ai/x)f(x)=\sum_{i=1}^{n}(a_i\%x+a_i/x)f(x)=i=1∑n​(ai​%x+ai​/x)
$x$为正整数，求最小的$f(x)$

数据范围

n≤106,ai≤106n\le10^6,a_i\le10^6n≤106,ai​≤106

题解

开个桶，然后前缀和即可
对于所有的数枚举转移区间
复杂度$\mathcal{O}(nlogn)$
代码

#include
#include
#include
#include
#include
#define rg register
typedef long long ll;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;
}
template <typename T> inline void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const int maxn=2000001;
int n,a[maxn];
ll ans,ANS;
int main()
{read(n);for(rg int i=1;i<=n;i++){int x;read(x);a[x]++;ANS+=x;}ans=ANS;for(rg int i=1;i<=2000000;i++)a[i]+=a[i-1];for(rg int x=1;x<=1000000;x++){ll res=ANS;for(rg int i=x;i<=1000000;i+=x)res-=(ll)i/x*(a[i+x-1]-a[i-1])*(x-1);mind(ans,res);}print(ans);return 0;
}

总结

关键是要发现没有性质，于是只能暴力

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！