https://codeforces.com/contest/1114

E. Arithmetic Progression

 

题意：交互题。有一个打乱了的等差数列，公差大于 0。你可以发起询问，两种：询问是否有大于 x 的数；询问第 i 个数。求出数列中最小的数和公差。询问不超过 60 次。

随机

首先通过第一种询问查出最大的数。还剩下 30 次。

也就是可以随机得到数列中的30个数，显然需要用到的是排列后的差，这些差都是公差的倍数。

关键点就是直接求出这些差的gcd，也就是说这里假定这些数的gcd就是公差。

出错的概率约为 1.86185⋅10 − 91.86185·10 ^{- 9}。

下面是搬运的官方题解：

为方便起见，假设原数列为 {0,1,2,⋯ ,n−1}\{0,1,2,\cdots,n-1\}。

假设 我们可以选出 k 个元素。

令 SS 为选出的 k 个元素组成的集合，即 S={s1,s2,⋯ ,sk}S=\{s_1,s_2,\cdots,s_k\}。

令 allall 表示选出集合 SS 的总方案数。

令集合上的函数 D(S)D(S) 为集合 S 中相邻元素的差组成的集合 {s2−s1,s3−s2,⋯ ,sk−sk−1}\{s_2-s_1,s_3-s_2,\cdots,s_k-s_{k-1}\} 的 gcd，即 D(S)=gcd⁡(si−si−1∣2≤i≤k)D(S)=\gcd(s_i-s_{i-1}|2\le i\le k)。

令 PP 表示我们随机选出的 k 个元素满足相邻元素之差组成的集合的 gcd 为 1 的概率，即随机程序 AC 的概率。

令 f(x)f(x) 表示 x 整除上面随机产生的集合 SS 的 D(S)D(S) 的概率。

下面分为两部分证明。

第一部分：证明 P=∑i=1nf(i)⋅μ(i)P=\sum_{i=1}^nf(i)\cdot \mu(i)。其中 μ(i)\mu(i) 为莫比乌斯函数。

P=∑S[D(S)=1]all⇓P⋅all=∑S[D(S)=1]=∑S∑d∣D(S)μ(d)=∑S∑d=1n([d∣D(S)]⋅μ(d))=∑d=1n(μ(d)⋅∑S[d∣D(S)])⇓P=∑d=1n(μ(d)⋅∑S[d∣D(S)])all=∑d=1n(μ(d)⋅∑S[d∣D(S)])all)=∑d=1nμ(d)⋅f(d)\begin{align} P &= \frac{\sum_S[D(S)=1]}{all}\\ &\Downarrow\\ P\cdot all &= \sum_S[D(S)=1]\\ &= \sum_S\sum_{d|D(S)}\mu(d)\\ &= \sum_S\sum_{d=1}^n ([d|D(S)]\cdot\mu(d))\\ &= \sum_{d=1}^n (\mu(d)\cdot\sum_S[d|D(S)])\\ &\Downarrow\\ P&= \frac{\sum_{d=1}^n (\mu(d)\cdot\sum_S[d|D(S)])}{all}\\ &= \sum_{d=1}^n (\mu(d)\cdot \frac{\sum_S[d|D(S)])}{all})\\ &= \sum_{d=1}^n \mu(d)\cdot f(d)\\ \end{align}

第二部分：求解 f(x)f(x)。

对于一个数 x，它能够整除 D(S)D(S) 说明 SS 中所有数模 x 同余，即 si≡si−1(mod  x)s_i\equiv s_{i-1}(\mod x)。

故令 g(r)g(r) 表示 选择大小为 k 的集合 SS，且满足对所有 1≤i≤k1\le i \le k 都有 si≡r(mod  x)s_i\equiv r(\mod x) 的方案数，其中 0≤r<x0\le r< x。

则由定义可知：

f(x)=∑r=0x−1g(r)allf(x)=\frac{\sum_{r=0}^{x-1}g(r)}{all}\\

g(r)g(r) 实际上是从所有模 x 等于 r 的元素组成的集合中选择 k 个。即从 ar={r,x+r,2x+r,⋯ }a_r=\{r,x+r,2x+r,\cdots\} 中选 k 个的方案数，即 Csizeof(ar)kC_{sizeof(a_r)}^k.

令 q=⌊nx⌋q=\lfloor\frac{n}{x}\rfloor。

若 r<(nmod  x)r<(n\mod x)，则 ara_r 包含 q+1q+1 个元素，此时方案数为 Cq+1kC_{q+1}^k.

若 (nmod  x)≤r<x(n\mod x)\le r<x，则 ara_r 包含 qq 个元素，此时方案数为 CqkC_q^k.

又容易得到 all=Cnkall=C_n^k。

所以

f(x)=∑r=0x−1g(r)all=(nmod  x)⋅Cq+1k+(n−nmod  x)⋅CqkCnk\begin{align} f(x) &= \frac{\sum_{r=0}^{x-1}g(r)}{all}\\ &= \frac{(n\mod x)\cdot C_{q+1}^k+(n-n\mod x)\cdot C_{q}^k}{C_n^k}\\ \end{align}

所以可以 O(1)\mathcal{O}(1) 计算出 f(x)f(x)。

综上，可以 O(n)\mathcal{O}(n) 枚举 d，对于每次枚举 O(1)\mathcal{O}(1) 得到结果，总的复杂度为 O(n)\mathcal{O}(n)。

出题人给出了他写的计算程序。

以及 1−P1-P 的结果

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;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
#define random(a,b) uniform_int_distribution<int> ((a), (b))(mt)
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
int n;
int t[N], f[N];
vector<int>vc;
int gcd(int a, int b) {
	if (a < b)swap(a, b);
	return b == 0 ? a : gcd(b, a%b);
}
int main() {
	scanf("%d", &n);
	int L = 0, R = 1000000000;
	while (L < R) {
		int mid = (L + R) / 2;
		cout << "> " << mid << endl;
		int o;
		cin >> o;
		if (o == 1)L = mid + 1;
		else R = mid;
	}
	for (int i = 1; i <= n; i++)t[i] = i;
	shuffle(t + 1, t + n + 1, mt);
	int m = min(n, 25);
	for (int i = 1; i <= m; i++) {
		cout << "? " << t[i] << endl;
		int x;
		cin >> x;
		vc.push_back(x);
	}
	sort(vc.begin(), vc.end());
	for (int i = 1; i < m; i++)f[i] = vc[i] - vc[i - 1];
	int d = f[1];
	for (int i = 2; i < m; i++)d = gcd(d, f[i]);
	cout << "! " << R - d * (n - 1) << ' ' << d << endl;
	return 0;
}

 

F. Please, another Queries on Array?

 

题意：给定一个数列，1≤ai≤3001 \le a_i \le 300，两种操作：把 [l,r][l,r] 中所有数都乘以 x，1≤x≤3001 \le x \le 300；询问 [l,r][l,r] 中所有数的欧拉函数的乘积 φ(∏i=lrai)\varphi(\prod \limits_{i=l}^{r} a_i)。

欧拉函数+线段树

欧拉函数是积性函数，即对于互质的两个数 n,mn,m，φ(n⋅m)=φ(n)⋅φ(m)\varphi(n\cdot m)=\varphi(n)\cdot\varphi(m)。

虽然这里没什么用，因为本题的数并不一定互质。

φ(n)=n⋅(1−1p1)⋅(1−1p2)⋯(1−1pm)\varphi(n)=n\cdot(1-\frac{1}{p_1})\cdot(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})，其中 n=p1k1⋅p2k2⋯pmkmn=p_1^{k_1}\cdot p_2^{k_2}\cdots p_m^{k_m}。

所以 φ(n1⋅n2)=n1⋅n2⋅(1−1p1)⋅(1−1p2)⋯(1−1pm)\varphi(n_1\cdot n_2)=n_1\cdot n_2\cdot (1-\frac{1}{p_1})\cdot(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})，所以需要维护两部分，第一部分直接乘积，第二部分维护新值的质因子。

由于数据范围只有300，质数个数大约只有60个，所以可以直接给每个数一个longlong记录它的质因子。

线段树维护区间操作，两个lazy。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
int n, q;
int a[N];
ll phi[400], prime[400], p_sz, d, val[400];
bool vis[N];
ll pr[400];
void get_phi(int n) {
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			pr[i] = (1ll << p_sz);
			prime[p_sz++] = i;
			phi[i] = i - 1;
		}
		for (ll j = 0; j < p_sz && (d = i * prime[j]) <= n; ++j) {
			vis[d] = 1;
			pr[d] |= pr[i];
			if (i % prime[j] == 0) {
				phi[d] = phi[i] * prime[j];
				break;
			}
			else {
				phi[d] = phi[i] * (prime[j] - 1);
				pr[d] |= (1ll << j);
			}
		}
	}
}
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll tr[N << 2], laz[N << 2], trp[N << 2], lazp[N << 2];
ll Pow(ll a, ll b) {
	ll res = 1ll;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
void up(int rt) {
	tr[rt] = tr[rt << 1] * tr[rt << 1 | 1] % mod;
	trp[rt] = trp[rt << 1] | trp[rt << 1 | 1];
}
void build(int l, int r, int rt) {
	laz[rt] = 1; lazp[rt] = 0;
	if (l == r) {
		tr[rt] = a[l];
		trp[rt] = pr[a[l]];
		return;
	}
	build(lson);
	build(rson);
	up(rt);
}
void down(int l, int r, int rt) {
	ll& x = laz[rt], &y = lazp[rt];
	if (x != 1 || y != 0) {
		int l1 = mid - l + 1, l2 = r - mid;
		tr[rt << 1] = tr[rt << 1] * Pow(x, l1) % mod;
		tr[rt << 1 | 1] = tr[rt << 1 | 1] * Pow(x, l2) % mod;
		laz[rt << 1] = laz[rt << 1] * x%mod;
		laz[rt << 1 | 1] = laz[rt << 1 | 1] * x%mod;
		trp[rt << 1] |= y;
		trp[rt << 1 | 1] |= y;
		lazp[rt << 1] |= y;
		lazp[rt << 1 | 1] |= y;
		x = 1; y = 0;
	}
}
void upd(int x, int ql, int qr, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		tr[rt] = tr[rt] * Pow(x, r - l + 1) % mod;
		laz[rt] = laz[rt] * x%mod;
		trp[rt] |= pr[x];
		lazp[rt] |= pr[x];
		return;
	}
	down(l, r, rt);
	if (ql <= mid)upd(x, ql, qr, lson);
	if (qr > mid)upd(x, ql, qr, rson);
	up(rt);
}
typedef pair<ll, ll>pii;
pii qry(int ql, int qr, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		return pii(tr[rt], trp[rt]);
	}
	down(l, r, rt);
	ll res1 = 1ll, res2 = 0;
	if (ql <= mid) {
		pii p = qry(ql, qr, lson);
		res1 = res1 * p.first%mod;
		res2 |= p.second;
	}
	if (qr > mid) {
		pii p = qry(ql, qr, rson);
		res1 = res1 * p.first%mod;
		res2 |= p.second;
	}
	return pii(res1, res2);
}
char op[100];
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	get_phi(300);
	for (int i = 0; i < p_sz; i++) {
		val[i] = (prime[i] - 1)*Pow(prime[i], mod - 2) % mod;
	}
	build(1, n, 1);
	while (q--) {
		scanf("%s", op);
		if (op[0] == 'M') {
			int l, r, x;
			scanf("%d%d%d", &l, &r, &x);
			upd(x, l, r, 1, n, 1);
		}
		else {
			int l, r;
			scanf("%d%d", &l, &r);
			pii p = qry(l, r, 1, n, 1);
			ll res = p.first;
			for (int i = 0; i < p_sz; i++) {
				if (p.second >> i & 1)res = res * val[i] % mod;
			}
			printf("%lld\n", res);
		}
	}
	return 0;
}