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;
}