https://codeforces.com/contest/1334

D. Minimum Euler Cycle

 

题意：一个n阶有向完全图，求出一个环经过每条边一次，且路径的字典序最小。要求输出路径的L到R段。

模拟

显然把小点先走完是最优解。

假设有5个点。则12131415232425343545.

那么难点就在输出了，先找到L在哪个大段，再确定小段，再加到R，加的时候注意跳段。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int N = 3e5 + 10;
int T;
ll n, l, r;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld%lld", &n, &l, &r);
		if (l == (n - 1)*n + 1) { puts("1"); continue; }
		ll p = 1, t = 1;
		for (ll i = 1; i < n&&p <= l; i++) {
			if (p > l)break;
			t++;
			p += 2 * (n - i);
		}
		if (p <= l)p++;
		t--;
		ll rs = n - (p - l) / 2 + 1;
		if (!(l & 1)) {
			l++;
			if (rs == t + 1)printf("%lld ", n);
			else {
				printf("%lld ", rs - 1);
				if (rs - 1 == n)t++, rs = t + 1;
			}
		}
		while (l <= r && t < n) {
			if (l & 1)printf("%lld ", t);
			else {
				printf("%lld ", rs);
				if (rs == n)t++, rs = t + 1;
				else rs++;
			}
			l++;
		}
		if (l <= r)printf("1");
		puts("");
	}
	return 0;
}

 

E. Divisor Paths

 

题意：给定数D，D的所有因子作为图的节点，若图上两个数商为质数，则连无向边，边权为两数的因子个数差。多次询问，每次给定图上两数，问最短路径条数。

组合数学

最短路径一定经过gcd。

假设一条路径上点递增，d(u)d(u) 为 uu 的因子数，则路径权值为 d(u1)−d(u)+d(u2)−d(u1)+d(v)−d(u2))=d(v)−d(u)d(u1)-d(u)+d(u2)-d(u1)+d(v)-d(u2))=d(v)-d(u)。

可能的最短路径有两种 u−>gcd−>vu->gcd->v 或者 u−>lcm−>vu->lcm->v，但是由于lcm的因子增加得太多了，所以所以 2d(lcm)−(d(u)+d(v))2d(lcm)-(d(u)+d(v)) 一定严格大于 d(u)+d(v)−2d(gcd)d(u)+d(v)-2d(gcd)，所以最短路只会是 u−>gcd−>vu->gcd->v。

得到上面结论的同时也把路径分成了两段，u−>gcdu->gcd 和 gcd−>vgcd->v，两段各自的路径数相乘得到答案。

u到gcd的过程就是把u中多于gcd中的质因子去掉，路径数与去掉的顺序有关，是一个可重复的排列数。v到gcd类似。

这里可以不用处理出gcd，而是处理只出u和v的质因子，对于每个质因子少的那个就是gcd。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 998244353;
ll D, u, v;
int q, cnt[2][110];
vector<ll>vc;
ll fac[N], inv[N];
ll power(ll a, int x) {
	ll ans = 1;
	while (x) {
		if (x & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		x >>= 1;
	}
	return ans;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i %mod;
	}
	inv[N - 1] = power(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
void solve(ll x, int id) {
	for (int i = 0; i < (int)vc.size(); i++) {
		if (x%vc[i] == 0) {
			while (x%vc[i] == 0) {
				x /= vc[i];
				cnt[id][i]++;
			}
		}
	}
}
int main() {
	scanf("%lld%d", &D, &q);
	init();
	for (ll i = 2; i*i <= D; i++) {
		if (D%i == 0) {
			vc.push_back(i);
			while (D%i == 0)D /= i;
		}
	}
	if (D > 1)vc.push_back(D);
	while (q--) {
		ll ans = 1, sum = 0;
		scanf("%lld%lld", &u, &v);
		memset(cnt, 0, sizeof(cnt));
		solve(u, 0);
		solve(v, 1);
		for (int i = 0; i < (int)vc.size(); i++) {
			if (cnt[0][i] < cnt[1][i]) {
				ans = ans * inv[cnt[1][i] - cnt[0][i]] % mod;
				sum += cnt[1][i] - cnt[0][i];
			}
		}
		ans = ans * fac[sum] % mod;
		sum = 0;
		for (int i = 0; i < (int)vc.size(); i++) {
			if (cnt[0][i] > cnt[1][i]) {
				ans = ans * inv[cnt[0][i] - cnt[1][i]] % mod;
				sum += cnt[0][i] - cnt[1][i];
			}
		}
		ans = ans * fac[sum] % mod;
		printf("%lld\n", ans);
	}
	return 0;
}