[思维]Ironforge 2022杭电多校第8场 1005

Problem Description

\space \space  A finer blade has never been crafted by my hand. I only hope it does not come too late... A gryphon rider brought word to me only moments ago... ...King Terenas is dead, lads. Killed by Arthas' own hand. You have my condolences. And though they won't bring back your king... Perhaps this blade will administer some justice, return some semblance o' order to the turmoil that grips your kingdom. Terenas was a good man, wise and just. Know that the dwarves o' Ironforge will mourn his passing.                                                

                                                                                                         —— 《Birth of Ashbringer》

The subway of Ironforge can been seen as a chain of n \geq 2n≥2 vertices. In other words, for each i=1,2,3...n-1i=1,2,3...n−1, there is an edge between vertex ii and vertex i+1i+1.

There is a number a_i(1 \leq i\leq n)ai​(1≤i≤n) on vertex ii and a prime number b_i(1\leq i < n)bi​(1≤i

You may start a trip on some vertex with an empty bag. When you are on vertex ii, you can put all prime factors of a_iai​ into your bag. You can walk through an edge with prime number pp written on it if and only if you already have pp in your bag. You are allowed to pass each vertex and each edge multiple times.

You need to answer mm queries. In each query you are given two numbers x,yx,y. You need to answer whether you can reach vertex yy if you start your trip on vertex xx by the subway of Ironforge.

Input

The input consists of multiple test cases.

The first line contains an integer T\ (1\leq T\le 3)T (1≤T≤3) denoting the number of test cases.

For each test case, the first line contains two integers nn and mm (2\leq n,m \leq 2\times 10^5)(2≤n,m≤2×105), denoting the number of vertices and the number of queries.

The second line contains nn integers a_i\ (1\leq i\leq n, 1 \leq a_i\leq 2\times 10^5)ai​ (1≤i≤n,1≤ai​≤2×105).

The third line contains n-1n−1 integers b_i\ (1\leq i < n, 2 \leq b_i\leq 2\times 10^5)bi​ (1≤i

Following mm lines describe the queries. Each line contains two integers x,y\ (1\leq x,y\leq n)x,y (1≤x,y≤n).

Output

For each query, output one line containing "Yes" if its possible to reach vertex yy from vertex xx and "No" otherwise.

Sample Input

1

5 5

7 1 6 6 14

7 2 3 2

1 2

1 4

3 5

5 1

3 1

Sample Output

Yes

No

Yes

Yes

Yes

题意： 给出n个城市，这些城市排成一条长链，相邻两城市间有边权bi，每个城市有一个点权ai，当处在一个城市时可以将ai的质因子装入背包，当要经过具有边权bi的边时必须背包中存在bi，背包中的质因子不会被消耗，之后有q组询问，每次询问给出起点和终点，问能否从起点走到终点。

分析： 可以先预处理出来从i只向右能走到的最远位置r[i]，之后从左向右枚举每个城市，求出以其为起点能走到的最远边界l[i]和r[i]，对于最左侧的城市1，它的左边界就是1，右边界就是之前处理出来的r[1]，从2~n枚举城市，如果不能从第i个城市走到第i-1个城市，那么l[i] = i，r[i]就是之前预处理的r[i]，如果能从第i个城市走到第i-1个城市且第i-1个城市也能走到第i个城市，那说明第i个城市的范围和第i-1个城市的范围是一样的，l[i] = l[i-1]，r[i] = r[i-1]，剩下一种情况就是能从第i个城市走到第i-1个城市但是没法从第i-1个城市走到第i个城市，这时候就需要暴力向左右扩展了，不过也并不是完全暴力，当能够走到城市j时，那说明一定也能走到l[j]和r[j]，所以这个过程被n个城市平均下来是O(n)的。最后一个问题就是怎么判断能不能走到下一个城市了，这可以通过一个vector数组维护出来每个质因子出现的位置，然后二分查询，例如要想知道在区间[l, r]时能否移动至l-1，那就找一下l到l-1那条边的边权bi在vector[bi]中第一个大于等于l的位置，如果它小于等于r，那就说明这段区间内出现过bi，也就可以走过去。最后整个问题的时间复杂度为O(nlogn)。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int a[200005], b[200005], l[200005], r[200005];
vector<int> p[200005]; 
 
bool check(int pri, int l, int r){
	vector<int>::iterator pos = lower_bound(p[pri].begin(), p[pri].end(), l);
	if(pos == p[pri].end()) return false;
	if(*pos <= r) return true;
	return false;
}
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, q;
		for(int i = 1; i <= 200000; i++) p[i].clear();
		scanf("%d%d", &n, &q);
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]); 
			int t = a[i];
			for(int j = 2; j <= t; j++){
				if(t%j == 0) p[j].push_back(i);
				while(t%j == 0)
					t /= j;
			}
			if(t != 1) p[t].push_back(i);
		}
		for(int i = 1; i < n; i++)
			scanf("%d", &b[i]);
		for(int i = n; i >= 1; i--){
			r[i] = i;
			for(int j = i+1; j <= n; j++){
				if(check(b[j-1], i, j-1)){
					j = r[j];
					r[i] = j;
				}
				else break;
			}
		}
		for(int i = 1; i <= n; i++){
			l[i] = i;
			if(i == 1) continue;
			if(r[i-1] >= i){//i-1能走到i 
				if(check(b[i-1], i, r[i])){
					l[i] = l[i-1];
					r[i] = r[i-1];
				}
			}
			else{//没法从i-1走到i 
				while(true){
					bool final = true;
					//向左
					for(int j = l[i]-1; j >= 1; j--){
						if(check(b[j], l[i], r[i])){
							j = l[j];
							l[i] = j;
							final = false;
						}
						else break;
					} 
					//向右 
					for(int j = r[i]+1; j <= n; j++){
						if(check(b[j-1], l[i], r[i])){
							j = r[j];
							r[i] = j;
							final = false;
						}
						else break;
					} 
					if(final) break;
				}
			}
		}
		for(int i = 1; i <= q; i++){
			int s, e;
			scanf("%d%d", &s, &e);
			if(l[s] <= e && r[s] >= e) puts("Yes");
			else puts("No");
		}
	} 
    return 0;
}