【数学水题】【TOJ4113】【 Determine X】-白红宇

【数学水题】【TOJ4113】【 Determine X】

阅读量：6574 次

发布时间：2019-06-24

本文共 1368 字，大约阅读时间需要 4 分钟。

题目大意：

yuebai has a long sequence of integers A1,A2,…,AN.

He also has such a function:

F (x) = \sum i = 1 N (⌊ A i x ⌋ + A i mod x)

x is a positive integer, which determined by yuebai.

Now he wants to know the minimum value of the function.

求一个x 使F[x]最大

解：

从1枚举到10^6

可知当X超过10^6 方后值就不变了

SB了

以为能快速求出的是sigma(Aimodx)。。。

发现傻逼了能快速求出的事 sigma(Aimodx)modx。。

预处理好a[i] 表示 A[i]中数值小于i的个数

以N/X的时间求出sigmafloor((Ai/x));

然后利用sigmafloor((Ai/x))+sigma(Aimodx)=sigma(Ai) 求出 sigma(Aimodx)

然后更新答案

代码如下：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define oo 0x13131313using namespace std;const int maxn=1000000+5;int N;int A[maxn],a[maxn];int MAX;long long sum=0;void input(){ memset(A,0,sizeof(A)); memset(a,0,sizeof(a)); cin>>N; MAX=-1; sum=0; for(int i=1;i<=N;i++) { scanf("%d",&A[i]); a[A[i]]++; if(A[i]>MAX) MAX=A[i]; sum+=A[i]; } for(int i=1;i<=MAX;i++) { a[i]=a[i]+a[i-1]; }}void solve(){ long long ans=1LL<<30; long long tt=0,g; for(int i=1;i<=MAX;i++) { int x=i;tt=0; for(int t=2*x;t-1<=MAX;t+=x) { int p=t-1; long long k=(long long)(a[p]-a[p-x])*(long long)(p/x); tt=tt+k; g=p; } tt=tt+(long long)(a[MAX]-a[g])*(long long)(MAX/x); tt=tt+sum-tt*(long long)x; if(tt
             
              >T; while(T--) { input(); solve(); }}