# 【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.

## 代码

```  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，偶然看到自己这篇超长题解和代码，这题没那么烦吧。。因为六个月前的训练赛又挂了这题，然后重写的代码：

``` 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

• ### 【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...

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

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

• ### POJ--1936 All in All（水题，暴力即可）

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

• ### LeetCode Weekly Contest 28解题思路

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

• ### FZU Moon Game(几何)

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