当前位置：首页 > news >正文

Codecraft-17 and Codeforces Round 391 E. Bash Plays with Functions 积性函数

news 来源：原创 2025/8/25 0:00:19

题目链接

题目大意

定义函数 $f_r(n)$ :

在 $r = 0$ 时，为满足 $p$ $\cdot$ $q = n$ , 且 $g c d (p, q) = 1$ 的有序对 $(p, q)$ 个数；
在 $r$ $\geq$ $1$ 时， $f_r(n)=$ $\sum_{u⋅v=n}$ $f_{r-1}(u)+f_{r-1}(v) \over 2$ 。
一共 $q$ 组询问，每组询问给出 $r$ , $n$ , 求 $f_r(n)$ 模 $10^{9}+7$ 的结果。
数据范围： $q\leq10^{6}$ , $0$ $\leq$ $r$ $\leq$ $10^{6}$ , $1$ $\leq$ $n$ $\leq$ $10^{6}$ 。

思路

积性函数
如果函数 $f$ : $N \to R$ ，满足对于任意一对互质的正整数 $p$ , $q$ 都有 $f (pq) = f (p) f (q)$ , 则称 $f$ 为积性函数。
若 $f$ 为积性函数，假设 $n={p_1}^{\alpha1}$ ${p_2}^{\alpha2}$ $\cdot$ $\cdot$ $\cdot$ ${p_k}^{\alpha k}$ , 则 $f(n)=f({p_1}^{\alpha1})$ $f({p_2}^{\alpha2})$ $\cdot$ $\cdot$ $\cdot$ $f({p_k}^{\alpha k})$ .

设 $n={p_1}^{\alpha1}$ ${p_2}^{\alpha2}$ $\cdot$ $\cdot$ $\cdot$ ${p_k}^{\alpha k}$ , 令 $x$ $\cdot$ $y$ $= n$ , 且 $g c d (x, y) = 1$ . 对于所有 ${p_i}^{\alpha i}$ 在 $x$ 、 $y$ 中的分配都为 ${p_i}^{0}$ 和 ${p_i}^{\alpha i}$ ，否则 $g c d (x, y)$ $\neq$ $1$ , 故 $f_0(n)=2^{k}$ 。

令 $\alpha(x)$ = $x$ 的质因数的种类，则当 $g c d (x, y) = 1$ 时， $f_0(xy)=2^{\alpha(xy)}$ $=2^{\alpha(x) \alpha(y)}$ = $2^{\alpha(x)}$ $\cdot$ $2^{\alpha(y)}$ $= f (x)$ $\cdot$ $f (y)$ ，故 $f_0(n)$ 为积性函数。

$f_r(n)=$ $\sum_{u\cdot v=n}$ $f_{r-1}(u)+f_{r-1}(v) \over 2$ , 如果 $u\neq$ $v$ , 则（ $u$ , $v$ ) 、( $v$ , $u$ ) 各出现一次，否则 $u = v$ , ( $u$ , $u$ ) 出现一次但一次有两个。故， $\forall$ $d$ , $d ∣ n$ , 都出现了两次，即 $f_r(n)=$ $\sum_{d|n}$ $f_{r-1}(d)$ .

令 $g_r(n)=$ $\sum_{d|n}$ $f_r(d)$ 。
证： $f_r(n)$ 为积性函数时， $g_r(n)$ 也为积性函数。

设 $p$ $\cdot$ $q$ $= n$ , $g c d (p, q) = 1$ , 则 $g_r(pq)=$ $\sum_{d|pq}$ $f_r(d)$ . 令 $d=d_1$ $\cdot$ $d_2$ , $d_1$ $∣ p$ , $d_2$ $∣ q$ , 则 $g_r(pq)=$ $\sum_{d|pq}$ $f_r(d)=$ $\sum_{d_1|p,d_2|q}$ $f_r(d_1d_2)=$ $\sum_{d_1|p,d_2|q}$ $f_r(d_1)$ $f_r(d_2)=$ $\sum_{d_1|p}$ $f_r(d_1)$ $\cdot$ $\sum_{d_2|q}$ $f_r(d_2)=$ $g_r(p)$ $\cdot$ $g_r(q)$ . 故当 $f_r(n)$ 为积性函数时， $g_r(n)$ 也为积性函数。

因为 $f_0(n)$ 是积性的不断递推 $f_r(n)$ 也将得到是积性的。

设 $n={p_1}^{\alpha1}$ ${p_2}^{\alpha2}$ $\cdot$ $\cdot$ $\cdot$ ${p_k}^{\alpha k}$ , 由于 $f_r(n)$ 是积性函数，则 $f_r(n)=$ $f_r({p_1}^{\alpha1})$ $\cdot$ $f_r({p_2}^{\alpha2})$ $\cdot$ $\cdot$ $\cdot$ $f_r({p_k}^{\alpha k})$ .

写几个函数看看规律：
$f_0(p^k)=\begin{cases} 1 & k=0 \\ 2 & k\geq 1 \\ \end{cases}$

$f_1(p^k)=$ $\sum_{d|p^k}$ $f_0(d)=$ $1 + 2 k$ .
$\cdot \cdot \cdot$
发现 $f_r(p^k)$ 只与 $r$ 和 $k$ 有关。

记： $d p [i] [j]$ 为 $f_i(p^j)$ 。初始化： $d p [i] [0] = 1$ , $dp[0][i]=2(i\geq1)$ .
转移时按定义来， $dp[i][j]=\sum_{x=0}^{j}$ $d p [i - 1] [x]$ , 加一个前缀和数组即可。

code

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>using namespace std;
const int N = 1e6 + 1000, mod = 1e9 + 7;
int prime[N], sum[N], cnt = 0, minnp[N];
bool st[N];
int dp[N][25];void is_prime(int n)
{for (int i = 2; i <= n; ++i){if (!st[i])prime[cnt++] = i, minnp[i] = i;for (int j = 0; j < cnt && i * prime[j] <= n; ++j){st[i * prime[j]] = 1, minnp[i * prime[j]] = prime[j];if (i % prime[j] == 0)break;}}
}void init()
{is_prime(1e6 + 10);for (int i = 0; i <= 1e6; ++i)dp[i][0] = 1;for (int i = 1; i <= 20; ++i)dp[0][i] = 2;sum[0] = 1;for (int i = 1; i <= 1e6; ++i){for (int j = 1; j <= 20; ++j){sum[j] = (sum[j - 1] + dp[i - 1][j]) % mod;dp[i][j] = sum[j];}}
}
void solve()
{int r, n;cin >> r >> n;int ans = 1;while (n >= 2){int num = 0, p = minnp[n];while (n % p == 0)num++, n /= p;ans = ans * dp[r][num] % mod;}// for (int i = 0; i < cnt && prime[i] <= sqrt(n); ++i)// {//     int num = 0;//     while (n % prime[i] == 0)//     {//         num++;//         n /= prime[i];//     }//     ans = ans * dp[r][num] % mod;// }// if (n > 1)//     ans = ans * dp[r][1] % mod;cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);init();int t = 1;cin >> t;while (t--)solve();return 0;
}

题目大意

思路

code

相关文章：