Primes and Multiplication Codeforces1228C 题目链接：https://codeforces.com/contest/1228/problem/C
思路
prime( x ) : x 的质因数g (x,p) : x的能被p整除的最大因数（如果p为质数可以理解为x质因数分解后p出现的次数 ）f (x,k)= g (k, prime(x) )f(x,1) * f(x,2) * f(x,3) * … f(x,n) = g(1, prime(x) ) * g(2, prime(x) ) * g(3, prime(x) ) * … g(n,prime(x) );上式 = g( n!, prime(x) )，于是可以参考 n! 的质因数分解方法 : (1). 先求出x 的质因数,即 prime(x) = p1,p2,…pk (2). 对每个质因数
p
i
p_{i}
pi g (n! ,
p
i
p_{i}
pi) =
p
i
m
pi^{m}
pim 其中 m =
⌊
n
p
i
⌋
\lfloor\frac{n}{pi}\rfloor
⌊pin⌋+
⌊
n
p
i
2
⌋
\lfloor\frac{n}{pi^2}\rfloor
⌊pi2n⌋+
⌊
n
p
i
3
⌋
\lfloor\frac{n}{pi^3}\rfloor
⌊pi3n⌋+… (3). 程序中
m
i
m_{i}
mi = get(n,
p
i
p_{i}
pi) 最后答案 ans =
p
1
m
1
p_{1}^{m_{1}}
p1m1 *
p
2
m
2
p_{2}^{m_{2}}
p2m2 *
p
3
m
3
p_{3}^{m_{3}}
p3m3 * … *
p
k
m
k
p_{k}^{m_{k}}
pkmk （% mod）
代码
#include
<iostream
>
#include
<vector
>
using namespace std
;
typedef long long
LL;
const LL MOD = 1e9 + 7;
int x
;
LL n
;
LL mpow(LL x
, LL n
)
{
LL res
= 1;
while (n
> 0)
{
if (n
& 1)
res
= (res
* x
) % MOD;
x
= (x
* x
) % MOD;
n
>>= 1;
}
return res
;
}
LL get(LL n
, LL p
)
{
LL s
= 0;
while (n
)
s
+= n
/ p
, n
/= p
;
return s
;
}
int
main()
{
scanf("%d%lld", &x
, &n
);
vector
<int
> v
;
for (int i
= 2; i
* i
<= x
; i
++)
{
if (x
% i
== 0)
{
while (x
% i
== 0)
{
x
/= i
;
}
v
.push_back(i
);
}
}
if (x
> 1)
{
v
.push_back(x
);
}
LL ans
= 1;
for (int i
= 0; i
< v
.size(); i
++)
{
ans
= (ans
* mpow((LL) v
[i
], get(n
, (LL) v
[i
]) ) ) % MOD;
}
printf("%lld\n", ans
);
}
