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

题目链接

题目大意

定义函数 $f_r(n)$ :

• 在$r=0$时，为满足 $p$ $\cdot$ $q=n$ , 且 $gcd(p,q)=1$ 的有序对 $(p,q)$ 个数；
• 在$r$ $\ge$ $1$时，$f_r(n)=$ ${\sum }_{u\cdot v=n}$ $\frac{f_{r-1}(u)+f_{r-1}(v)}{2}$。
  一共 $q$ 组询问，每组询问给出 $r$ , $n$ , 求 $f_r(n)$ 模 $10^9+7$ 的结果。
  数据范围：$q\le 10^6$,$0$ $\le$ $r$ $\le$ $10^6$,$1$ $\le$ $n$ $\le$ $10^6$。

思路

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

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

令 $\alpha (x)$=$x$ 的质因数的种类，则当 $gcd(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}$$\frac{f_{r-1}(u)+f_{r-1}(v)}{2}$ , 如果 $u\ne$ $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$,$gcd(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_1{d}_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}^{\alpha 1}$${p_2}^{\alpha 2}$ $\cdot$ $\cdot$ $\cdot$ ${p_k}^{\alpha k}$ , 由于$f_r(n)$是积性函数，则 $f_r(n)=$$f_r({p_1}^{\alpha 1})$ $\cdot$ $f_r({p_2}^{\alpha 2})$ $\cdot$ $\cdot$ $\cdot$ $f_r({p_k}^{\alpha k})$ .

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

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

记：$dp[i][j]$为 $f_i(p^j)$ 。初始化：$dp[i][0]=1$ , $dp[0][i]=2(i\ge 1)$.
转移时按定义来，$dp[i][j]={\sum }_{x=0}^j$$dp[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;
}