https://codeforces.com/contest/1366

D. Two Divisors

 

题意：给定一个数，要求找出它的两个因子 d1,d2，且他们的和与这个数互质。多次询问。

设 x=p1k1⋅p2k2⋯pmkmx=p_1^{k_1}\cdot p_2^{k_2}\cdots p_m^{k_m}，则构造出第一个因子为 p1p_1，第二个因子为 p2k2⋯pmkmp_2^{k_2}\cdots p_m^{k_m}。

假设 gcd(d1+d2,x)≠1gcd(d1+d2,x)\neq 1，则 gcd 一定是 x 的某个因子，则一定有一个 x 的质因子整除 gcd，设为 p，则一定有 (d1+d2)%p=0(d1+d2)\% p=0 ，即 (p1+p2k2⋯pmkm)%p=0(p_1+p_2^{k_2}\cdots p_m^{k_m})\%p=0，其中 p 是 p1,p2,⋯ ,pmp_1,p_2,\cdots,p_m 中的一个。

若 p=p1p=p_1，则 (p1+p2k2⋯pmkm)%p=(p2k2⋯pmkm)%p≠0(p_1+p_2^{k_2}\cdots p_m^{k_m})\%p=(p_2^{k_2}\cdots p_m^{k_m})\%p\neq 0。

若 p≠p1p\neq p_1，则 (p1+p2k2⋯pmkm)%p=p1%p≠0(p_1+p_2^{k_2}\cdots p_m^{k_m})\%p=p_1\%p\neq 0

所以假设不成立。

把 p1p_1 换成任意的 pip_i 也都是一样的，所以只要找到任意一个质因子即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 5e5 + 10;
int n;
int a[N], vis[10000010];
int b[N], c[N];
int main() {
	for (int i = 2; i < 10000010; i++) {
		if (vis[i])continue;
		for (int j = i + i; j < 10000010; j += i) {
			vis[j] = i;
		}
	}
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (!vis[a[i]])b[i] = c[i] = -1;
		else {
			int x = vis[a[i]];
			while (a[i] % x == 0) {
				a[i] /= x;
			}
			if (a[i] == 1)b[i] = c[i] = -1;
			else b[i] = x, c[i] = a[i];
		}
	}
	for (int i = 1; i <= n; i++)printf("%d%s", b[i], i == n ? "\n" : " ");
	for (int i = 1; i <= n; i++)printf("%d%s", c[i], i == n ? "\n" : " ");
	return 0;
}

 

E. Two Arrays

 

题意：给定数组 a 和数组 b ，且 b 递增，要把 a 分成 k 段，每段非空，且第 i 段的最小值等于 b[i]。

双指针

预处理出后缀最小值。

要放置k-1个隔板，第 i 个隔板能放的范围为后缀最小值=b[i+1] 的区间。

唯一的问题是两个隔板可放的范围是否会交叉？

由于 b 递增，且后缀最小值也是递增，所以如果第 i 个隔板放到了第 i-1 个的范围内，则交叉的范围内后缀最小值=b[i]，而不是 b[i+1] ，所以第 i 个隔板不可能放到这个范围内。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
int n, m;
int a[N], b[N];
ll ans = 1ll;
int s[N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++)scanf("%d", &b[i]);
	s[n] = a[n];
	for (int i = n - 1; i >= 1; i--)s[i] = min(a[i], s[i + 1]);
	int L = n, R = n, p = m;
	while (p > 1) {
		int tmp = 0;
		while (s[L] >= b[p]) {
			if (s[L] == b[p])tmp++;
			L--;
		}
		if (s[L + 1] != b[p]) { puts("0"); return 0; }
		ans = ans * tmp % mod;
		p--;
		R = L;
	}
	if (s[1] != b[1]) { puts("0"); return 0; }
	printf("%lld\n", ans);
	return 0;
}