CF757E Bash Plays with Functions
原题链接：E. Bash Plays with Functions
Tag：数论、DP
题目描述
定义一个函数 \(f_r(n)\)：
在 \(r = 0\) 时， \(f_0(n)\) 的取值为满足 \(a \times b = n\) 并且 \(\gcd(a,b) = 1\) 的有序对 \((a,b)\) 的个数。
在 \(r \geq 1\) 时， \(f_r(n) = \sum\limits_{u \cdot v=n}\frac{f_{r-1}(u)+f_{r-1}(v)}{2}\)。
一共 \(q\) 组询问， 每组询问给出 \(r\)，\(n\) 求 \(f_r(n)\bmod10^9+7\) 的结果。
数据说明： \(q\le10^6\),\(0\le r\le10^6\),\(1\le n\le10^6\)。
分析
首先我们分析 \(r = 0\) 时， 如何求解 \(f_0(n)\)。 考虑一下题目中给出的 \(f_0(r)\) 的定义， \(\gcd(a,b) = 1\) 也就是说 \(a\) 与 \(b\) 是互质的， 这代表 \(a\) 与 \(b\) 没有公共的质因子。 又因为 \(a \times b = n\)， 不难想到 \(a\) 和 \(b\) 两个数字瓜分了 \(n\) 的质因子。 由于每个因子要么属于 \(a\) 要么属于 \(b\)， 也就是说 \(f_0(n)\) 的答案为 \(2^{\omega(n)}\)。
考虑到 \(\omega(n)\) 的定义， 可以考虑 \(\omega(n)\) 的某些性质， 即当 \(\gcd(a,b) = 1\) 时， \(\omega(a) + \omega(b) = \omega(a*b)\)。
对于 \(2^{\omega(n)}\) 这个式子而言， \(\omega(n)\) 是一个加性函数 (Additive Function)， 把一个加性函数放在次幂上， 次幂的加法等于整体的乘法， 于是我们可以得出 \(2^{\omega(n)}\) 即 \(f_0(n)\) 是一个积性函数。
考虑完了 \(r = 0\) 的情况我们来考虑一下 \(r \geq 1\) 的时候， 根据题意有：
可以看到，在这种情况下题目没有要求 \(u\) 与 \(v\) 互质。 所以我们可以引入一个 \(x = u\)，就可以把式子化成这种形式：
观察化简之后的式子，我们发现其中的 \(x\) 和 \(\frac{n}{x}\) 是呈现对称关系的， 于是可以进一步化简成
这是一个狄利克雷卷积的形式，由于积性函数集对狄利克雷卷积封闭， 所以当 \(f_{r-1}(n)\) 为积性函数时， \(f_r(n)\) 也是积性函数。 因为前文证明了 \(f_0(n)\) 是一个积性函数， 所以可以递归证明 \(f_r(n)\) 也是一个积性函数。
考虑完了 \(f_r(n)\) 的积性函数，我们开始考虑如何计算。 首先根据我们对于 \(f_0(n)\) 的分析， 我们先考虑一种 \(n\) 只有一种质因子的情况， 这个时候 \(f_0(p^k) = 2\)，因为这一个质因子要么属于 \(a\) 要么属于 \(b\)。 于是可以想到 \(f_r(p^k)\) 的答案和 \(p\) 并没有关系， 答案仅由 \(r\) 与 \(k\) 相关。
因为前文证明了 \(f_r(n)\) 是一个积性函数， 不难想到在对 \(n\) 质因子分解之后， 将 \(n\) 分解成 \(p_1^{k_1} p_2^{k_2} \cdots p_{i-1}^{k_{i-1}} p_i^{k_i}\) 就可以写成 \(f_r(n) = \prod\limits_{k=1}^{\omega(n)}f_r(p^k)\)。 于是我们考虑如何计算 \(f_r(p^k)\) 就可以了。
于是我们可以考虑 \(dp\)， 我们设 \(dp_{i,j}\) 的意义为当 \(r = i\)，\(k = j\) 时 \(f_r(p^k)\) 的答案，就可以转移了。
当计算答案时，我们需要对 \(n\) 的每个质因子分别考虑， 在这里如果直接暴力质因子分解会TLE，因此我们 \(\Theta(nloglogn)\) 筛预处理一下值域内所有数字的最大质因子。 之后做一个 \(O(nlogn)\) 的 \(dp\)，这里我为了方便第二维固定为了19。 最后可以在 \(O(\Omega(n))\) 的时间内求解单组答案。
代码实现
int dp[N][20];
int tmp[N];
void NeverSayNever() {
for (int i = 2; i <= 1e6 ; ++i) {
if(tmp[i] == 0){
for (int j = i; j <= 1e6; j += i) {
tmp[j] = i;
}
}
}
dp[0][0] = 1;
for (int i = 1; i <= 19; ++i) {
dp[0][i] = 2;
}
for (int i = 1; i <= 1e6; ++i) {
dp[i][0] = 1;
for (int j = 1; j <= 19; ++j) {
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
}
}
int T; cin >> T;
while(T--){
int n,r; cin >> r >> n;
int ans = 1;
while(n != 1){
int rec = tmp[n];
int cnt = 0;
while(n % rec == 0){
n /= rec;
cnt++;
}
ans *= dp[r][cnt];
ans %= MOD;
}
cout << ans << endl;
}
}
额外思考
数学真难
日志
本页面创建于 2024/7/19 10:06
特别鸣谢：
Ackerlanna、 Kilo_5723、 kawaii0922 、 RDDCCD 提供的格式指导。
UPD-1：2024/8/26 13:26
在walk_alone的指点下进行了格式修改，并修正若干笔误。