这场CF我网炸了 然后赛后补题 这道题应该算是魔改一下阶乘质因数分解 题意翻译直接搬洛谷的了懒得打
首先我们可以把$x$质因数分解 然后考虑$x$的因子$p$
对于每一个$p$ 我们都要求出$g(1,p)\cdot g(2,p)\cdots g(n,p)$ 而$g(x,p)$的含义其实就是对于$x$质因数分解后的$p^k$所以我们可以按阶乘分解那么考虑 考虑每个因子$p$对于答案的贡献 首先考虑$p$ 显然有$\lfloor \frac{n}{p} \rfloor$个数至少包含一个$p$ 那么贡献就是$p^{\lfloor \frac{n}{p} \rfloor}$
之后再考虑$p^2$ 有$\lfloor \frac{n}{p^2} \rfloor$个数可以分解出$p^2$ 但由于之前我们在统计$p$时已经加了一遍 所以这时候的贡献不需要乘2 只需要再加上$\lfloor \frac{n}{p^2} \rfloor$就好了
以此类推 总共需要统计$\log_{p}{n}$次 记贡献总数为$t$ 那么该$p$对答案的贡献便是$p^t$ 之后快速幂统计即可 要注意的是在统计贡献数时有可能会爆long long（实际上不会）我们不用考虑那么多 因为$t$是次幂不能直
接%mod 但是我们有欧拉定理 我们把次幂%phi(mod)答案是不变的 因为题目给的mod是$1e9+7$所以直接%(mod-1)即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll x,n;
vector<ll> prime;
ll ksm(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
cin>>x>>n;
for(ll i=2;i<=x/i;i++)
{
if(x%i==0)
{
prime.push_back(i);
while(x%i==0) x/=i;
}
}
if(x>1) prime.push_back(x);
ll l=prime.size();
ll ans=1;
for(int i=0;i<l;i++)
{
ll p=prime[i];
ll t=n,t1=0;
while(t)
{
t1=(t1+t/p)%(mod-1);
t/=p;
}
ans=(ans%mod*ksm(p,t1)%mod)%mod;
}
cout<<ans<<endl;
return 0;
}
|