题目描述

原题传送门
对于一个正整数 ​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

输入

2 3
2 1
5 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;
}