https://ac.nowcoder.com/acm/contest/9510

B - 最小的指数

 

题意：T,1≤T≤100000T,1\le T\le100000 次询问，每次给定数 n,1≤n≤1018n,1\le n\le 10^{18}，令 n=p1a1p2a2⋯pkak,a1,a2,⋯ ,ak>0n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},a_1,a_2,\cdots,a_k>0，问 min⁡{a1,a2,⋯ ,ak}\min\{a_1,a_2,\cdots,a_k\}。

因数分解

对于这种 nn 很大的题目，如果要分解质因数，首先就应该考虑能否只枚举一个小范围内的质因子。

枚举 [2,5000][2,5000] 的质数，暴力分解，最终 nn 只包含 >5000>5000 的质因子。

如果 ans=4ans=4，说明 nn 中存在 p4p^4，且其它因子的幂次都 ≥4\ge 4，但是如果有两个质因子，这就不可能发生，所以只可能有 n=p4n=p^4，因此需要判断 nn 的四次根号是否为整数。

如果 ans=3ans=3，与上面相同，只可能是 n=p3n=p^3，因此需要判断 nn 的三次根号是否为整数。

如果 ans=2ans=2，可能有 n=p2n=p^2 或者 n=p12⋅p22n=p_1^2\cdot p_2^2，这时只要判断 nn 是否是完全平方数。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int prime[N], vis[N], tot;
void sieve(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			prime[++tot] = i;
		}
		ll d;
		for (int j = 1; j <= tot && (d = i * prime[j]) <= n; j++) {
			vis[d] = 1;
			if (i%prime[j] == 0)break;
		}
	}
}
ll Pow(ll x, ll b) {
	ll res = 1;
	for (int i = 0; i < b; i++)res *= x;
	return res;
}
int T;
int main() {
	sieve(5000);
	scanf("%d", &T);
	while (T--) {
		ll n;
		scanf("%lld", &n);
		if (n == 1) { puts("0"); continue; }
		int ans = INF;
		for (int i = 1; i <= tot; i++) {
			if (n%prime[i] == 0) {
				int cnt = 0;
				while (n%prime[i] == 0) {
					cnt++;
					n /= prime[i];
				}
				ans = min(ans, cnt);
			}
		}
		if (n != 1) {
			ll x = llround(pow(1.0*n, 0.25));
			bool flg = 0;
			for (int i = -10; i <= 10; i++) {
				if (x*x*x*x == n) { flg = 1; break; }
			}
			if (flg) { printf("%d\n", min(ans, 4)); continue; }

			x = llround(pow(1.0*n, 1.0 / 3.0));
			for (int i = -10; i <= 10; i++) {
				if (x*x*x == n) { flg = 1; break; }
			}
			if (flg) { printf("%d\n", min(ans, 3)); continue; }

			x = llround(pow(1.0*n, 0.5));
			for (int i = -10; i <= 10; i++) {
				if (x*x == n) { flg = 1; break; }
			}
			if (flg) { printf("%d\n", min(ans, 2)); continue; }
			printf("1\n");
		}
		else printf("%d\n", ans);
	}
	return 0;
}

 

C - 排列

 

题意：有一个 nn 的排列，超级逆序对数为 KK，问猜中这个排列的概率。超级逆序对：满足 i<ji<j 且 ai>aj+1a_i>a_j+1 的二元组 (i,j)(i,j)。

dp

dp[i][j][k]dp[i][j][k] 表示前 ii 个数，有 jj 个超级逆序对，且 11 的位置在 kk 的方案数。

可以先考虑普通的逆序对。dp[i][j]dp[i][j] 表示前 ii 个数，有 jj 个超级逆序对的方案数。

前 ii 个数的情况由前 i−1i-1 个数时的情况转移得到，把前 i−1i-1 个数都 +1+1，则原本的逆序对数不变，现在要插入数字 11，插在位置 kk，则新增 k−1k-1 个逆序对，虽然我们要枚举 11 的位置，但是不需要记录下来。这样只要二维dp就能搞定。

再考虑超级逆序对，前 i−1i-1 个数转移到前 ii 个数时我们把所有数+1，再插入 11，但是这时新增逆序对数不等于 k−1k-1，因为 (2,1)(2,1) 这时不算逆序对了。所以还要记录前 i−1i-1 个数时 11 的位置。所以dp增加一维。

dp[i][j][k]=∑p=1k−1dp[i−1][j−k+2][p]+∑p=ki−1dp[i−1][j−k+1][p]dp[i][j][k]=\sum_{p=1}^{k-1}dp[i-1][j-k+2][p]+\sum_{p=k}^{i-1}dp[i-1][j-k+1][p]\\

发现可以前缀和优化掉两个 ∑\sum。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n, K;
ll Pow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		b >>= 1;
		a = a * a%mod;
	}
	return res;
}
ll dp[510][510], tmp[510][510];

int main() {
	scanf("%d%d", &n, &K);
	dp[0][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= min(i*(i - 1) / 2, K); j++) {
			for (int k = 1; k <= i; k++) {
				tmp[j][k] = dp[j][k];
				dp[j][k] = 0;
			}
		}
		for (int j = 0; j <= min(i*(i - 1) / 2, K); j++) {
			for (int k = 1; k <= i; k++) {
				if (j - k + 2 >= 0)dp[j][k] = (dp[j][k] + tmp[j - k + 2][k - 1]) % mod;
				if (j - k + 1 >= 0)dp[j][k] = (dp[j][k] + tmp[j - k + 1][i - 1] - tmp[j - k + 1][k - 1] + mod) % mod;
			}
			for (int k = 1; k <= i; k++)dp[j][k] = (dp[j][k] + dp[j][k - 1]) % mod;
		}
	}
	printf("%lld\n", Pow(dp[K][n], mod - 2));
	return 0;
}

 

D - 数列

 

题意：给定一个数组，问多少个区间满足：区间中每个数都出现了 kk 的倍数次。

哈希

记录在 [1,i][1,i] 中 xx 出现的次数 cnt[i][x]cnt[i][x]，则区间 [i,j][i,j] 满足条件等价于 cnt[i−1][1]≡cnt[j][1]mod  kcnt_[i-1][1]\equiv cnt[j][1]\mod k，cnt[i−1][2]≡cnt[j][2]mod  kcnt_[i-1][2]\equiv cnt[j][2]\mod k，⋯\cdots。

对 {cnt[i][1]%k,cnt[i][2]%k,⋯ }\{cnt[i][1]\%k,cnt[i][2]\%k,\cdots\} 哈希，则区间左右端点的哈希值必须相同。

哈希方式很多，比如题解里是给每个数字随机一个值，或者每个数字分配一个幂次 pw[i]pw[i]，但是这个 pw[i]pw[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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
#define random(a,b) uniform_int_distribution<int> ((a), (b))(mt)
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
int n, k;
int a[N], cnt[N];
map<ll, int>cc;
ll hsh[N], ans, hah[N];
int main() {
	for (int i = 1; i < N; i++)hah[i] = random(10212, 219320329);
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		cnt[a[i]]++;
		hsh[i] = hsh[i - 1] - (cnt[a[i]] - 1) % k*hah[a[i]] + cnt[a[i]] % k*hah[a[i]];
	}
	cc[0]++;
	for (int i = 1; i <= n; i++) {
		ans += cc[hsh[i]];
		cc[hsh[i]]++;
	}
	printf("%lld\n", ans);
	return 0;
}

 

E - 反演

 

题意：定义 F(m,n)=∑i=1n∑j∣mσ0(ij)F(m,n)=\sum\limits_{i=1}^n\sum\limits_{j|m}\sigma_0(ij)。其中 σ0(n)=∑i=1n[n%j==0]\sigma_0(n)=\sum\limits_{i=1}^n[n\%j==0]，即 nn 的因子个数。给定 n,mn,m，求 F(m!,n)F(m!,n)，1≤n≤1011,1≤m≤1001\le n\le 10^{11},1\le m\le 100。

莫比乌斯反演+推式子

先来看 F(m,n)F(m,n)。

F(m,n)=∑i=1n∑j∣mσ0(ij)\begin{align} F(m,n) &= \sum_{i=1}^n\sum_{j|m}\sigma_0(ij)\\ \end{align}

i⋅ji\cdot j 的因子都可以分解成 x⋅yx\cdot y，其中 x∣i,y∣jx|i,y|j，为了保证不重复统计，必须还要有 gcd⁡(x,y)=1\gcd(x,y)=1。

所以

F(m,n)=∑i=1n∑j∣m∑x∣i∑y∣j[gcd⁡(x,y)=1]F(m,n) = \sum_{i=1}^n\sum_{j|m}\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\\

改变次序，把 x,yx,y 放到最前面。

这时就要考虑对于每一对 (x,y)(x,y)，它们被统计了几次。

xx 被 i=x,2x,3x,⋯⌊nx⌋xi=x,2x,3x,\cdots \lfloor\frac{n}{x}\rfloor x 时统计到，yy 被 y∣j,j∣my|j,j|m 时统计到。xx 的比较简单，yy 对应的 jj 的个数其实是 σ0(my)\sigma_0(\frac{m}{y})，也就是 jj 在 yy 的基础上还能乘哪些数使得仍有 j∣mj|m。

所以

F(m,n)=∑x=1n∑y∣m[gcd⁡(x,y)=1]⋅⌊nx⌋⋅σ0(my)F(m,n) = \sum_{x=1}^n\sum_{y|m}[\gcd(x,y)=1]\cdot\lfloor\frac{n}{x}\rfloor\cdot\sigma_0(\frac{m}{y})\\

莫比乌斯反演得到

F(m,n)=∑x=1n∑y∣m∑d∣gcd⁡(x,y)μ(d)⋅⌊nx⌋⋅σ0(my)=∑x=1n⌊nx⌋∑y∣mσ0(my)∑d∣gcd⁡(x,y)μ(d)\begin{align} F(m,n) &= \sum_{x=1}^n\sum_{y|m}\sum_{d|\gcd(x,y)}\mu(d)\cdot\lfloor\frac{n}{x}\rfloor\cdot\sigma_0(\frac{m}{y})\\ &= \sum_{x=1}^n\lfloor\frac{n}{x}\rfloor\sum_{y|m}\sigma_0(\frac{m}{y})\sum_{d|\gcd(x,y)}\mu(d)\\ \end{align}

把 dd 放到最前面

同样要考虑同一个 dd 被统计了几次。每次 xx 都为 dd 的倍数，而对于每个 xx 都乘了一个 ⌊nx⌋\lfloor\frac{n}{x}\rfloor，x=dx=d 时为 nd\frac{n}{d}，x=2dx=2d 时为 n2d\frac{n}{2d}，x=3dx=3d 时为 n3d\frac{n}{3d}，……，所以总贡献为 ∑i=1ndni⋅d\sum\limits_{i=1}^{\frac{n}{d}}\frac{n}{i\cdot d}，记为 S(nd)S(\frac{n}{d}).

F(m,n)=∑d∣m,d<nμ(d)S(nd)∑d∣y,y∣mσ0(my)F(m,n) = \sum_{d|m,d<n}\mu(d)S(\frac{n}{d})\sum_{d|y,y|m}\sigma_0(\frac{m}{y})\\

下面再考虑 F(m!,n)F(m!,n)。

即

F(m!,n)=∑d∣m!,d<nμ(d)S(nd)∑d∣y,y∣m!σ0(m!y)F(m!,n) = \sum_{d|m!,d<n}\mu(d)S(\frac{n}{d})\sum_{d|y,y|m!}\sigma_0(\frac{m!}{y})\\

把 dd 放在最前面的用处就在于只有质因子最高幂次为 11 的 dd，才产生贡献，所以可以暴力dfs枚举 dd，复杂度为 2252^{25}。

S(x)S(x) 可以数论分块求得。

设 x=p1k1p2k2⋯pmkmx=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}，我们知道因数个数 σ0(x)=(k1+1)(k2+1)⋯(km+1)\sigma_0(x)=(k_1+1)(k_2+1)\cdots(k_m+1)。

我们还知道 m!m! 中包含的 pp 的幂次为 t=m/p+m/p/p+m/p/p/p+⋯t = m/p+m/p/p+m/p/p/p+\cdots。

设 m!y=p1k1p2k2⋯pmkm\frac{m!}{y}=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}，则 m!y\frac{m!}{y} 中 p1p_1 可取到的幂次为 0,1,2,⋯ ,k10,1,2,\cdots,k_1。p2p_2 也类似。则 ∑d∣y,y∣m!σ0(m!y)\sum\limits_{d|y,y|m!}\sigma_0(\frac{m!}{y}) 可以用类似生成函数的方式表示成 (1+2+⋯+(k1+1))⋅(1+2+⋯+(k2+1))⋯(1+2+⋯+(km+1))(1+2+\cdots+(k_1+1))\cdot(1+2+\cdots+(k_2+1))\cdots(1+2+\cdots+(k_m+1))。

对于每个 dd 的质因子 pp，yy 为 dd 的倍数，所以 yy 中 pp 的幂次至少与 dd 中相同，则 m!y\frac{m!}{y} 包含的 pp 的幂次范围为 [0,t−1][0,t-1]，所以 pp 产生的贡献为 (1+2+⋯+t)(1+2+\cdots+t)。

而对于不是 dd 的质因子的质数 pp，m!y\frac{m!}{y} 包含的 pp 的幂次范围为 [0,t][0,t]，所以 pp 产生的贡献为 (1+2+⋯+t+t+1)(1+2+\cdots+t+t+1)。

枚举每一个质数，加入或不加入 dd，并据此及时计算 σ0(m!y)\sigma_0(\frac{m!}{y})，在最后一层计算 μ(d)S(nd)∑d∣y,y∣m!σ0(m!y)\mu(d)S(\frac{n}{d})\sum_{d|y,y|m!}\sigma_0(\frac{m!}{y})。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int vis[N], prime[N], tot, cnt[N];
void sieve(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			prime[++tot] = i;
			int x = n;
			while (x) {
				cnt[tot] += x / i;
				x /= i;
			}
		}
		int d;
		for (int j = 1; j <= tot && (d = i * prime[j]) <= n; j++) {
			vis[d] = 1;
			if (i%prime[j] == 0)break;
		}
	}
}
ll n;
int m;
ll S(ll n) {
	ll res = 0;
	for (ll l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		res = (res + (r - l + 1)*(n / l) % mod) % mod;
	}
	return res;
}
ll ans;
void dfs(int dep, ll d, int mu, ll the) {
	if (dep == tot + 1) {
		ans = (ans + mu * S(n / d)*the%mod + mod) % mod;
		return;
	}
	dfs(dep + 1, d, mu, (2 + cnt[dep])*(1 + cnt[dep]) / 2 % mod*the%mod);
	if (d*prime[dep] <= n) {
		dfs(dep + 1, d*prime[dep], -mu, (1 + cnt[dep])*cnt[dep] / 2 % mod*the%mod);
	}
}
int main() {
	scanf("%lld%d", &n, &m);
	sieve(m);
	dfs(1, 1, 1, 1);
	printf("%lld\n", ans);
	return 0;
}