COCI20162017 Contest#6 F

其实这个题不是很难的。。。

设值域为$M$

考虑如果没有幸运数的限制，那么从$A$变成$B$，实际上只与$\frac{A} {B}$有关

不妨令$dp_{i,j}$为从$i$走了$j$步变成1，显然这个$j$的最大值为$\log M=19$，即$2^{19}$最多操作19次

从$i$枚举倍数进行转移，同时也暴力处理每个数的因数个数，复杂度为$O(M\ln M\log M)$

接下来考虑幸运数的限制

推论: 最多只会在一个幸运数上停留

如果经过多个，显然在代价最小的那个上面停留

因此考虑枚举停留的幸运数$x$

那么转移可以分为两步$\frac{A} {x}$和$\frac{x} {B}$，可以暴力合并两个$dp$数组，单次查询复杂度为$O(T\cdot \log^2 M)$

合并得到的结果，可以描述为:

可以在$x$上用$C(x)$的代价停留，并且其他部分的转移花了$j$的时间，$y$的代价

如果考虑停留的时间，那么得到的答案显然是一条直线，斜率就是停留的代价

关于一群直线，一群查询，不难想到可以斜率优化求解，这一部分复杂度为$O(T\log M\log (T\log M)+m)$（排序复杂度）

总复杂度可以认为就是$O(M\log^2 M+Q(T\log ^2 M+m))$

斜率优化的实现可以参考代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define reg register
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e6+10,INF=1e9;

int n,m;
int F[N],A[N],B[N];
int L[N];
// A: 因子个数
// B: 将B变成1需要的最大步数
int C[N],D[N];
int dp[N][20];
// 用了j步，将i变为1的最小代价

struct Node{ 
    // 描述一条直线
	ll x,y;
	// 答案为 x*i+y
	ll operator [](const ll i)const {
		return i*x+y;
	} //求直线点值
	bool operator < (const Node __) const {
		if(x!=__.x) return x<__.x;
		return y<__.y; //按照斜率排序
	}
} U[N];

int Uc,T[21],R[21];

int main(){
	rep(i,1,N-1) {
		A[i]++;
		for(reg int j=i+i;j<N;j+=i) A[j]++,cmax(B[j],B[i]+1);
	}
	rep(i,1,rd()) F[i]=rd();
	rep(i,1,m=rd()) L[i]=rd();
	sort(L+1,L+m+1);
	rep(i,1,N-1) rep(j,0,B[i]) dp[i][j]=INF;
	dp[1][0]=0;
	rep(i,1,N-1) rep(j,0,B[i]) if(dp[i][j]<INF) for(reg int k=i+i;k<N;k+=i) cmin(dp[k][j+1],dp[i][j]+F[A[k/i]]);
	rep(i,1,n=rd()) C[i]=rd(),D[i]=rd();

	rep(kase,1,rd()) {
		int x=rd(),y=rd(),d=x/y;
		if(x%y!=0){
			printf("%d\n",-m);
			continue;
		}
		memset(R,63,sizeof R);
		Uc=0;
		rep(i,1,n) if(x%C[i]==0 && C[i]%y==0){
			int dx=x/C[i],dy=C[i]/y;
			memset(T,63,sizeof T);
			rep(a,0,B[dx]) if(dp[dx][a]<INF) rep(b,0,B[dy]) cmin(T[a+b],dp[dx][a]+dp[dy][b]);
			rep(j,0,B[dx]+B[dy]) if(T[j]<INF) {
				ll a=D[i],b=T[j]-a*j;
				U[++Uc]=(Node){a,b};
				rep(k,j,B[d]) cmin(R[k],(int)U[Uc][k]);
			}
		}
		rep(i,0,B[d]) cmin(R[i],dp[d][i]);
		ll ans=0;
		ll mi=1e18;
		sort(U+1,U+Uc+1);
		int R=0;
		rep(i,1,Uc) {
			if(mi<U[i].y) continue;
			mi=U[i].y;
			while(R>1 && (U[i].y-U[R].y)*(U[R].x-U[R-1].x)<=(U[R].y-U[R-1].y)*(U[i].x-U[R].x)) R--;
			U[++R]=U[i]; // 单调栈处理凸包，注意加入时满足x递增，y递减
		}
		rep(i,1,m) if(L[i]<=B[d]) ans+=::R[L[i]]<INF?::R[L[i]]:-1;
		else {
			while(R>1 && U[R-1][L[i]]<=U[R][L[i]]) R--;
			if(!R) ans--;
			else ans+=U[R][L[i]];
		}
		printf("%lld\n",ans);
	}
}