【洛谷 P6786】 「SWTR-6」GCDs & LCMs

传送门

这道题其实乍一看很难,但其实就是一道推数学规律的题,只要把这个规律推出来了,剩下的也就很好办了。

最关键的就是题面中所给的那个式子,bi+bj+gcd(bi,bj)=lcm(bi,bj)b_i+b_j+\gcd(b_i,b_j)=\operatorname{lcm}(b_i,b_j),我们令x=gcd(bi,bj)x=\gcd(b_i,b_j)pi=bi÷xp_i=b_i\div xpj=bj÷xp_j=b_j\div x,则根据最小公因数和最大公倍数的定义可以得到:

pix+pjx=xpipjxpi+pj=pipj1pipjpipj+1=2(pi1)(pj1)=2p_i\cdot x+p_j\cdot x=x\cdot p_i\cdot p_j-x\\ p_i+p_j=p_i\cdot p_j-1\\ p_i\cdot p_j-p_i-p_j+1=2\\ (p_i-1)\cdot(p_j-1)=2

很明显可以知道

piN+,pjN+p_i\in \mathbb{N_+},p_j\in\mathbb{N_+}

于是就可以推出

pi=2,pj=3p_i=2,p_j=3

所以

bi:bj=2:3b_i:b_j=2:3

也就是说,对于一个数,要么它是序列中最大的那个,要么就有另外一个数是它的32\dfrac{3}{2} 倍。

因此,对于选出来的序列b1,b2,b3,,bkb_1,b_2,b_3,\cdots,b_k,将其去重并从小到大排序后,应该满足32bi=bi+1\dfrac{3}{2}b_i=b_{i+1},也就是一个公比为32\dfrac{3}{2} 的等比数列,至于为什么是去重后,因为我们只关心这个数有没有比它大12\dfrac{1}{2} 的数,只要满足这个条件,无论有几个和这个数相同的数,我们都可以把它们放在序列里面,比如2,2,2,3,32,2,2,3,3 这个序列就是满足条件的。

这样,问题就转化成了,在给定序列中寻找一个公比为32\dfrac{3}{2} 的等比序列,并且这个序列中所有数的和最大。对于这个问题,我的思路是 DP,先对原序列进行排序和去重,用fif_i 表示以第ii 个数结尾的公比为32\dfrac{3}{2} 的等比数列中所有数的最大的和,状态转移方程也很好想,就是对于aia_i,找有没有aj=23aia_j=\dfrac{2}{3}a_i,如果有,那么fifj+fif_i\leftarrow f_j+f_i,如果没有,就不管它,由于事先已经对序列排序并去重,所以这个找的过程可以用二分解决(别跟我说桶排,10910^9 的值域你自己去排),时间复杂度为O(nlogn)O(n\log n),对付3×1053\times 10^5 的数据也够了。

至于预处理,在去重的时候顺便解决一下就好了,具体的可以看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
int n,k,a[300001],b[300001];//a 是原数组,b 是去重后的数组
long long ans,f[300001];
int check(int l,int r,int val)//二分查找,如果有值为 val 的数则返回下标,没有则返回 -1
{
while(l<=r)//记得一定要有等于!!!
{
int mid=(l+r)/2;
if(b[mid]==val)
return mid;
if(b[mid]>val)
r=mid-1;
if(b[mid]<val)
l=mid+1;
}
return -1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);//排序
for(int i=1;i<=n;i++)
{
if(a[i]!=a[i-1])//去重
b[++k]=a[i];
f[k]+=a[i];//预处理,如果和上一个数相同,就自动加到一起
}
for(int i=1;i<=k;i++)
{
if(b[i]%3==0)//一定要有这个条件!
{
int t=check(1,i,b[i]/3*2);
if(t!=-1)
f[i]+=f[t];
}
ans=max(ans,f[i]);
}
printf("%lld",ans);
return 0;
}

【洛谷 P6786】 「SWTR-6」GCDs & LCMs

http://www.azusemisa.top/posts/3151199811.html

作者

AzuSemisa

发布于

2020-08-24

更新于

2020-08-25

许可协议

评论