牛客竞赛-小红的约数

2024年08月14日 924 字大概 4 分钟

涉及几何级数、费马小定理、逆元。

题目描述
题解
代码

题目描述

原题传送门
对于一个正整数 $n$ 和一个非负整数 $d$，定义 $f_d(n)$ 为 $n$ 的所有约数的 $d$ 次方之和。如 $f_3(10) = 1^3 + 2^3 + 5^3 + 10^3$。
现给定 $n,d$，求 $f_d(n)$ 的值。由于答案可能很大，输出答案对 $10^9 + 7$ 取模的结果。
输入描述:

由于 $n$ 可能很大，所以给出 $n$ 的质因数分解式。
$n = \prod_{i=1}^{w} p_i^{a_i}$
第一行输入一个正整数 $w$ 和一个非负整数 $d$。
接下来 $w$ 行，每行输入两个正整数 $p_i, a_i$。
保证 $p_i$ 为素数且互不相同。
对于全部的测试点，保证 $1 \leq w \leq 10^5, 0 \leq d \leq 10^9, 2 \leq p_i \leq 10^9, 1 \leq a_i \leq 10^9$。

输出描述:

输出 $f_d(n)$ 对 $10^9 + 7$ 取模的结果。

示例1

输入
1
2
3
2 3
2 1
5 1
输出
1
1134
说明
$f_3(10) = 1^3 + 2^3 + 5^3 + 10^3 = 1134$。

题解

根据题目的描述，要求计算 $f_d(n)$，对于每一个质因数 $p_i$，$n$ 可以写成它的质因数乘积形式：

$$n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_w^{a_w}$$
对于每个质因数 $p_i$：
$$
f_d(p_i^{a_i}) = 1^d + p_i^d + \left(p_i^2\right)^d + \cdots + \left(p_i^{a_i}\right)^d
$$
可以化简为一个几何级数：
$$
f_d(p_i^{a_i}) = \frac{p_i^{d(a_i+1)} - 1}{p_i^d - 1}
$$

情况 1：如果 $p_i^d \equiv 1 \pmod{10^9 + 7}$，则：
$$
f_d(p_i^{a_i}) = 1 + 1 + \cdots + 1 = a_i + 1
$$

情况 2：如果 $p_i^d \not\equiv 1 \pmod{10^9 + 7}$，则：
$$
f_d(p_i^{a_i}) = \frac{(p_i^d)^{a_i+1} - 1}{p_i^d - 1} \bmod{10^9 + 7}
$$

由于在模运算中不能直接进行除法，因此需要计算模逆元：

什么是模逆元？

对于一个整数 $a$ 和一个模数 $m$，如果存在一个整数 $x$，使得：
$$
a \times x \equiv 1 \pmod{m}
$$
那么这个 $x$ 就被称为 $a$ 在模 $m$ 意义下的逆元，记作 $a^{-1} \mod m$。

费马小定理与模逆元

如果 $m$ 是一个质数，费马小定理告诉我们，对于任意不为 $m$ 倍数的整数 $a$，有：

$$
a^{m-1} \equiv 1 \pmod{m}
$$

将这个等式两边同时乘以 $a^{-1}$，得到：

$$
a^{m-2} \equiv a^{-1} \pmod{m}
$$

因此，模逆元可以表示为：

$$
a^{-1} \equiv a^{m-2} \pmod{m}
$$

这意味着我们可以通过快速幂计算 $a$ 的 $m-2$ 次方对 $m$ 取模，来得到 $a$ 在模 $m$ 意义下的逆元。

推导

设 $m=10^9+7$ 上式可写成

$$
\begin{aligned}
f_d(p_i^{a_i}) &= \frac{(p_i^d)^{a_i+1} - 1}{p_i^d - 1} \bmod{m} \\
&= {((p_i^d)^{a_i+1} - 1) \times (p_i^d - 1)}^{-1} \bmod{m} \\
&= ((((p_i^d)^{a_i+1} - 1) \bmod{m}) \times ({(p_i^d - 1)}^{-1} \bmod{m})) \bmod{m} \\
&= ((((p_i^d)^{a_i+1} \bmod{m}) - 1) \times ({(p_i^d - 1)}^{-1} \bmod{m})) \bmod{m} \\
&= ((((p_i^d)^{a_i+1} \bmod{m}) - 1) \times ({(p_i^d - 1)}^{m-2} \bmod{m})) \bmod{m} \\
\end{aligned}
$$

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;

const ld pi=acos(-1);
const ld eps=1e-4;
const ll mod=1e9+7;

ll qpow(ll a, ll b,ll m=mod) {
    ll result=1;
    while (b) {
        if (b&1) result=result*a%m;
        a=a*a%m;
        b>>=1;
    }
    return result;
}

void solve() {
    ll w,d;cin>>w>>d;
    ll ans=1;
    while(w--) {
        ll p,a;cin>>p>>a;
        ll q=qpow(p,d);
        if(q==1) ans=ans*(a+1)%mod;
        else ans*=(qpow(q,a+1)-1)*qpow(q-1,mod-2)%mod,ans%=mod;
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}