EERound2 相同的数字

链接：https://www.luogu.com.cn/problem/P6104 题目描述：对于一个长为$n$的序列。 将$a_{i}$变为$a_{i}+1$需要$c1$的代价 将$a_{i}$变为大于$a_{i}$的最小质数需要$c2$的代价 求将整个数列变为同一个值的最小代价，多组询问。 题解：话说这题不开$long long$怎么$10$分，考场上把我坑惨了，$100->10$。 首先，我们发现其实我们可以将原问题转化为一个$DAG$，这个问题其实就是在求$DAG$的最近公共祖先。 事实上，我们假设所有的点都挪至大于$a_{i}$的最小质数处，此时一类边可以合并成一条"大边",此时我们只要求二类边与"大边"的贡献的最小值就行了，令"大边"边权为$d0$，二类边边权为$d1$,对于每一条边$i$的贡献即为$sz_{i}\times d0\times c1$或$sz_{i}\times d1\times c2$(其中$sz_{i}$表示$i$前面点的个数)。我们要的是最小值，实际上就是要满足$\frac{d0}{d1}<\frac{c2}{c1}$，这一个可以开小数类然后预处理前缀和二分答案。 当然所有的点都挪至大于$a_{i}$的最小质数处也是要讨论的，可以发现这一个问题和上一个问题其实是一样的，也可以这样维护。 当然，这还没完，存在所有数变为$a$的最大值的这种情况，这种情况也可以像上述那样讨论。 事实上其实你可以不开小数类，用$\lfloor \frac{c2}{c1} \rfloor$ 二分就可以了，你又可以发现$\lfloor \frac{c2}{c1} \rfloor$只有$n$种情况，预处理可以做到线性。 ``` #include #include #include using namespace std; struct node { long long a,b,s; bool operator < (const node &t)const { return a*t.b<b*t.a; }="" };="" node="" top[1000002],top2[1000002],top3[1000002],top4[1000002],tmp;="" long="" lastans0,n,q,t,res,a[200002],ps[20000001],leng;="" sum[1000002],sum2[1000002],sum3[1000002],sum4[1000002],sum5[1000002],sum6[1000002],lastans;="" int="" pos,v[10500001],prime[10500001],length;="" main()="" {="" scanf("%d%d%d",&n,&q,&t);="" for="" (int="" i="1;i<=n;++i)" scanf("%lld",&a[i]);="" sort(a+1,a+n+1);="" if="" (!v[i])="" v[i]="i;" prime[++length]="i;" j="1;j<=length;++j)" (prime[j]*i="">1e7+500000||prime[j]>v[i]) break; v[i*prime[j]]=prime[j]; } } for (int i=1;i<=n;++i) { while (prime[pos]<a[i]) pos++;="" top2[i].a="prime[pos]-a[i];" top2[i].b="1;" ps[pos]="i;" }="" for="" (int="" i="1;i<=pos-1;++i)" if="" (ps[i]="=0)" ps[i]="ps[i-1];" {="" (a[i]<prime[pos-1])="" top4[++leng]="top2[i];" else="" res+="(a[n]-a[i]);" top[i].b="1;" top[i].a="prime[i+1]-prime[i];" top[i].s="ps[i];" top3[i]="top[i];" sort(top+1,top+pos-1+1);="" sort(top2+1,top2+n+1);="" sort(top3+1,top3+pos-2+1);="" sort(top4+1,top4+leng+1);="" sum[i]="sum[i-1]+top[i].s*top[i].a;">=1;--i) sum2[i]=sum2[i+1]+top[i].s; for (int i=1;i<=n;++i) sum3[i]=sum3[i-1]+top2[i].a; for (int i=1;i<=pos-2;++i) sum4[i]=sum4[i-1]+top3[i].s*top3[i].a; for (int i=pos-2;i>=1;--i) sum5[i]=sum5[i+1]+top3[i].s; for (int i=1;i<=leng;++i) sum6[i]=sum6[i-1]+top4[i].a; int c1,c2,first,last,mid,ans; while (q--) { scanf("%d%d",&c1,&c2); c1=c1^(T*(lastans%(1<<17))); c2=c2^(T*(lastans%(1<<17))); tmp.a=c2; tmp.b=c1; first=1; last=pos-1; ans=0; while (first<=last) { mid=(first+last)/2; if (top[mid]