MZOJ #72 数字

分析

看题解：

说实话，可以不用从一开始一个一个枚举，枚举素数就好，合数可以拆分为素数的积

所以：线性筛又出来了

枚举gcd之后呢，怎么算代价?

肯定不可能一个一个枚举。

那我们看看两种操作，一是加1，而是删除

只能加不能减说明只要找到大于当前值的最小的gcd的倍数就可以找出“加”的最小代价，再与删除的代价比较就好

既然如此，我们为什么不批量操作呢？

看a的范围，完全可以用桶来装，再求前缀和，这样就可以解决“加”的问题了

怎么解决删除？

直接比较删除与加的分界线就好：

emmm，复杂度吗，大约n/2+n/3+n/5+……

反正不会超就对了

注意空间开两倍，因为最大值不一定是倍数，所以要用到后面的数

代码

  1 /**************************
  2 User:Mandy.H.Y
  3 Language:c++
  4 Problem:numbers
  5 Apgorithm:
  6 **************************/
  7 
  8 #include<bits/stdc++.h>
  9 
 10 using namespace std;
 11 
 12 const int maxn = 1e6 + 5;
 13 const int maxa = 2e6 + 5;
 14 
 15 typedef long long ll;
 16 
 17 long long n,c1,c2,ma = 0,ans,cnt;
 18 long long a[maxa],prime[maxa],s[maxa];
 19 //a是前缀和
 20 //s是个数 
 21 bool vis[maxa];
 22 
 23 template<class T>inline void read(T &x){
 24     x = 0;bool flag = 0;char ch = getchar();
 25     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 26     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 27     if(flag) x = -x;
 28 }
 29 
 30 template<class T>void putch(const T x){
 31     if(x > 9) putch(x / 10);
 32     putchar(x % 10 | 48);
 33 }
 34 
 35 template<class T>void put(const T x){
 36     if(x < 0) putchar('-'),putch(-x);
 37     else putch(x);
 38 }
 39 
 40 void file(){
 41     freopen("numbers.in","r",stdin);
 42     freopen("numbers.out","w",stdout);
 43 }
 44 
 45 
 46 void get_prime(){//线性筛 
 47 
 48     vis[0] = 1;
 49     vis[1] = 0;
 50     
 51     for(ll i = 2;i <= ma; ++ i){
 52         if(!vis[i]) prime[++cnt] = i;
 53         for(ll j = 1;j <= cnt && prime[j] * i <= ma; ++ j){
 54             vis[prime[j] * i] = 1;
 55             if(i % prime[j] == 0) break;
 56         }
 57     }
 58     
 59 }
 60 
 61 void readdata(){
 62     read(n);read(c1);read(c2);
 63     for(int i = 1;i <= n; ++ i){
 64         ll x;read(x);
 65         s[x]++;
 66         ma = max(ma,x);
 67     }
 68     
 69     for(int i = 1;i <= ma + ma; ++ i){//注意 两倍 
 70         a[i] = a[i-1] + s[i] * i;
 71     }
 72     
 73     for(int i = 1 ; i <= ma + ma ; ++ i)
 74         s[i] += s[i-1];
 75 }
 76 
 77 void work(){
 78     
 79     ans = n * min(c1,c2);
 80     
 81     for(ll i = 1;i <= cnt; ++ i){
 82         ll res = 0;
 83         ll j = 0;
 84         do{
 85             j += prime[i];
 86             ll tmp = c1/c2;
 87             ll r = max((long long)j - tmp - 1,j - prime[i]);
 88             //删除与加的分界线 
 89             res += (j * (s[j] - s[r]) - (a[j] - a[r])) * c2 + (s[r] - s[j-prime[i]]) * c1;
 90             if(res >= ans) break;
 91         }while(j <= ma);
 92         //j不一定小于ma，j的上限是大于等于ma的最小倍数 
 93         
 94         ans = min(ans,res);
 95     }
 96     
 97     put(ans);
 98 }
 99 
100 int main(){
101 //    file();
102     readdata();
103     get_prime();
104     work(); 
105     return 0;
106 }

View Code

非做顽石不可，哪管他敬仰暗唾