CF1228C Primes and Multiplication 题解

题目链接：CF1228C Primes and Multiplication

题意：

首先先介绍一些涉及到的定义：

定义 \(\mathbb{P}(x)\) 表示x的质因子集合。举例来说，\(\mathbb{P}(140) = \{2, 5, 7\}\)，\(\mathbb{P}(169) = \{13\}\)。

定义 \(g(x, p)\) 表示存在一个最大的 \(k \in \mathbb{N}_+\) ，使得 \(x\) 可以被 \(p^k\) 整除（ 即\(p^k \mid x \ \land\ p^{k+1}\not\mid x\) ），那么 \(g(x, p) = p^k\) 。举例来说：

• \(g(45, 3) = 9\) （ \(45\)可以被 \(3^2 = 9\) 整除但是不能被 \(3^3=27\) 整除）
• \(g(63, 7) = 7\) （ \(63\) 可以被 \(7^1 = 7\) 整除但是不能被 \(7^2=49\) 整除）

定义 \(f(x, y)\) 表示所有 \(g(y, p)~(p \in \mathbb{P}(x))\) 的乘积，举例来说：

• \(f(30, 70) = g(70,2)·g(70,3)·g(70, 5) = 2^1·3^0·5^1 = 10\)
• \(f(525,63) = g(63,3)·g(63,5)·g(63,7) = 3^2·5^0·7^1 = 63\)

现在给出两个整数 \(x\) 和 \(n\) ，请计算出 \(f(x,1)·f(x,2)\dots f(x,n)~\bmod~(10^9+7)\) 的值。

输入格式：

The only line contains integers \(x\) and \(n\) ( \(2 \le x \le 10^{9}\) , \(1 \le n \le 10^{18}\) ) — the numbers used in formula.

输出格式：

Print the answer.

可以发现其实就是给了我们一个 \(\mathbb{P}\) ，然后让我们求 \(\prod_{1 \le i \le n,~ p_j \in \mathbb{P}} g(i,p_j)\)

我们先来考虑 \(|\mathbb{P}|=1\) 的情况，也就是只有一个质因子 \(p\) 时的答案，容易发现其贡献为 \[ p^{n/p}\times p^{n/p^2} \times p^{n/p^3} \times\cdots \] 由于贡献的计算是相互独立的，所以多个 \(p\) 就多算几次就好了

时间复杂度 \(\mathcal{O}(\sqrt{n})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int cnt,res = 1,p[15];
int qpow(int a,int b)
{
    int ans = 1, base = a;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * base % mod;
        base = base * base % mod;
    }
    return ans;
}
void init(int x)
{
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0) {
            p[++cnt] = i; while(x % i == 0) x /= i;
        }
    if(x > 1) p[++cnt] = x;
}
void solve(int x,int n)
{
    for(; n; n /= x)
        res = res * qpow(x, n / x) % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int x,n; cin >> x >> n; init(x);
    for(int i = 1; i <= cnt; i++) solve(p[i], n);
    cout << res << '\n';
    return 0;
}