专栏首页饶文津的专栏【CodeForces 624D/623B】Array GCD

【CodeForces 624D/623B】Array GCD

You are given array ai of length n. You may consecutively apply two operations to this array:

  • remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
  • change some elements of the array by at most 1, and pay b coins for each change.

Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.

Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

Input

The first line of the input contains integers na and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.

The second line contains n integers ai (2 ≤ ai ≤ 109) — elements of the array.

Output

Print a single number — the minimum cost of changes needed to obtain an array, such that the greatest common divisor of all its elements is greater than 1.

Sample test(s)

input

3 1 4
4 2 3

output

1

input

5 3 2
5 17 13 5 6

output

8

input

8 3 4
3 7 5 4 3 12 9 4

output

13

Note

In the first sample the optimal way is to remove number 3 and pay 1 coin for it.

In the second sample you need to remove a segment [17, 13] and then decrease number 6. The cost of these changes is equal to 2·3 + 2 = 8 coins.

题意

给你n个数,可以执行两种操作最多各一次,一是移除一个连续的序列不可移动整个数列,代价是序列长度*a,二是选一些数改变1,即可以有的加一,有的减一,代价是数字个数*b

最终使得剩下所有数字的最大公约数大于1,求最少代价

分析

因为不能移除所有的数,所以a[1]和a[n]至少会有一个留下来,所以要在a[1]-1、a[1]、a[1]+1、a[n]-1、a[n]、a[n]+1六个数的所有质因数里找最大公约数。

找出t的所有质因子是j从2到根号t,如果t能整除j,j就是一个质因数,存起来,然后t一直除以j,除到不能整除为止,最后判断一下剩下的数如果大于1,那应该就是它本身了,那说明他就是一个素数,也要存起来。存的时候要注意不要重复。这样才不会超时,如果做素数表然后一个个素数去判断是不是它的因数就会超时。

找好后,对每个质因数,进行尺扫(或者叫尺取,还有种方法是DP(待补充)),左边扫到右边,预处理一下前i个数里有几个需要改变(bnum[i]),有几个必须移除的(anum[i])。

扫的时候,移除L到R这段区间的代价为aCost,不移除的代价为bCost,当bCost<=aCost时说明不用移除更划算,于是L更新为R+1,并且存下修改前面的数需要的代价oldbCost,否则计算一下只移除这段区间,其他区间通过修改达到目标,需要多少代价(oldbCost + aCost + ( bnum[n] - bnum[R] ) * b),然后更新答案。算代价的时候如果一个数必须移除,那修改的代价设为无穷。

代码

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #define ll long long
  4 #define N 1000005
  5 using namespace std;
  6 ll n,a,b,m[N],p[N],bnum[N],anum[N],primeFactorNum,minc=1e18;
  7 
  8 void savePrime(ll a)
  9 {
 10     int noSaved=1;
 11     for(int i=0; i<primeFactorNum && noSaved; i++)
 12         if(a==p[i])
 13             noSaved=0;
 14     if(noSaved)
 15         p[primeFactorNum++]=a;
 16 }
 17 
 18 void FindPrimeFactor(ll a)
 19 {
 20     for(int i=-1; i<=1; i++)
 21     {
 22         int j,t=a+i;
 23         for(j=2; j*j<=t; j++)
 24         {
 25             if(t%j==0)
 26             {
 27                 savePrime(j);
 28                 while(t%j==0)t/=j;
 29             }
 30         }
 31         if(t>1)
 32             savePrime(t);
 33     }
 34 }
 35 
 36 ll cost(ll num,ll factor)
 37 {
 38     if(num%factor==0)
 39         return 0;
 40     if( (num+1) % factor && (num-1) % factor )
 41         return 1e17;//+1或-1都不能整除factor
 42     return b;
 43 }
 44 
 45 void solve(ll factor)
 46 {
 47     ll L=1,R,bCost=0,aCost=0,oldbCost=0;
 48 
 49     while( cost(m[L],factor) == 0 && L <= n) L++;//左边过滤掉不需要改动的连续序列
 50     if(L == n+1)
 51     {
 52         minc=0;
 53         return;
 54     }
 55     R = L-1;
 56 
 57     bnum[0] = anum[0] = 0;
 58 
 59     for(int i=1; i<=n; i++)
 60     {
 61         ll tmp=cost(m[i],factor);
 62 
 63         if(tmp == b)
 64             bnum[i] = bnum[i-1]+1;
 65         else
 66             bnum[i] = bnum[i-1];
 67 
 68         if(tmp == 1e17)
 69             anum[i] = anum[i-1]+1;
 70         else
 71             anum[i] = anum[i-1];
 72     }
 73 
 74     if(anum[n] == 0)
 75         minc = min( minc, bnum[n] * b );
 76 
 77     while(R<n)
 78     {
 79         aCost+=a;
 80         R++;
 81         if(bCost<1e17)
 82             bCost+=cost(m[R],factor);
 83         if(bCost<=aCost)
 84         {
 85             L=R+1;
 86             oldbCost+=bCost;
 87             bCost=aCost=0;
 88         }
 89         else
 90         {
 91             if(anum[n]-anum[R]==0)
 92                 minc = min( minc , oldbCost + aCost + ( bnum[n] - bnum[R] ) * b );
 93         }
 94     }
 95 }
 96 int main()
 97 {
 98     scanf("%I64d%I64d%I64d",&n,&a,&b);
 99     for(int i=1; i<=n; i++)
100         scanf("%I64d",&m[i]);
101 
102     FindPrimeFactor(m[1]);
103     FindPrimeFactor(m[n]);
104 
105     for(int i=0; i<primeFactorNum && minc; i++)
106         solve(p[i]);
107 
108     printf("%I64d",minc);
109     return 0;
110 } 

 2017/8/14,偶然看到自己这篇超长题解和代码,这题没那么烦吧。。因为六个月前的训练赛又挂了这题,然后重写的代码:

当时写得变量名真色。。我快看不懂了。。no代表一个都没删除的最小代价,be表示删除了第i个的最小代价,t就是删除了第i-1个的最小代价,ov就是有删除过但第i-1个未必删除了的最小代价。算是dp的思路。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #define ll long long
 6 #define N 1000005
 7 #define inf (1LL<<60)
 8 using namespace std;
 9 int n,c[N],d[7],pr[N],cnt;
10 ll a,b;
11 int main() {
12     scanf("%d%lld%lld",&n,&a,&b);    
13     for(int i=1;i<=n;i++)
14         scanf("%d",&c[i]);
15     d[0]=c[1]-1,d[1]=c[1]+1;
16     d[2]=c[n]-1,d[3]=c[n]+1;
17     d[4]=c[1];d[5]=c[n];
18     for(int i=0;i<6;i++){
19         for(int j=2;j*j<=d[i];j++)
20             if(d[i]%j==0){
21                 pr[cnt++]=j;
22                 while(d[i]%j==0)
23                     d[i]/=j;
24             }
25         if(d[i]>1)pr[cnt++]=d[i];
26     }
27     sort(pr,pr+cnt);
28     int m=0;
29     pr[m++]=pr[0];
30     for(int i=1;i<cnt;i++)if(pr[i]!=pr[i-1])pr[m++]=pr[i];
31     ll ans=inf;
32     for(int i=0;i<m;i++){
33         ll no=0,be=0,ov=0;
34         for(int j=1;j<=n;j++){
35             ll t=be;
36             be=min(no+a,be+a);
37             if(c[j]%pr[i]){
38                 if((c[j]+1)%pr[i]==0||(c[j]-1)%pr[i]==0)
39                 {
40                     no+=b;
41                     ov=min(min(ov+b,t+b),t+a);
42                 }else{
43                     no=inf;
44                     ov=t+a;
45                 }
46             }else{
47                 ov=min(t,ov);
48             }
49         }
50         ans=min(ans,min(min(no,be),ov));
51     }
52     printf("%lld\n",ans);
53     return 0;
54 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Codeforces 738A】Interview with Oleg

    http://codeforces.com/contest/738/problem/A

    饶文津
  • 「2017 Multi-University Training Contest 7」2017多校训练7

    饶文津
  • 【CodeForces 602C】H - Approximating a Constant Range(dijk)

    In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional rai...

    饶文津
  • poj-1207 THE 3n+1 problem

    Problems in Computer Science are often classified as belonging to a certain clas...

    瑾诺学长
  • 浙江大学计算机与软件学院2019年保研上机模拟练习

    A happy number is defined by the following process: Starting with any positive i...

    glm233
  • HDU 1010 Tempter of the Bone【DFS经典题+奇偶剪枝详解】

    Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 6553...

    Angel_Kitty
  • POJ--1936 All in All(水题,暴力即可)

    All in All Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 3...

    ShenduCC
  • LeetCode Weekly Contest 28解题思路

    好吧,不要被这道题的例子给骗了。要求输出的最大,意思就是求除第一个元素之外的其他division最小,而不断连除就是第二部分的最小值,所以有如下代码:

    用户1147447
  • FZU Moon Game(几何)

    Accept: 710    Submit: 2038 Time Limit: 1000 mSec    Memory Limit : 32768 KB  P...

    ShenduCC
  • 聊聊flink的AbstractNonHaServices

    flink-runtime_2.11-1.7.1-sources.jar!/org/apache/flink/runtime/highavailability/...

    codecraft

扫码关注云+社区

领取腾讯云代金券