题面
题目描述
输入
两个非负整数A,B
输出
仅一个正整数，表示答案
样例输入
2 3
样例输出
15
数据范围
提示
题解
这道题有N个结论
第一：A可分解为
P
1
b
1
P
2
b
2
.
.
.
P
n
b
n
P1^{b1}P2^{b2}...Pn^{bn}
P1b1P2b2...Pnbn（分解质因数） 第二：首先，第一点是正确的，其次，
A
B
A^B
AB可表示为
P
1
b
1
∗
B
P
2
b
2
∗
B
.
.
.
P
n
b
n
∗
B
P1^{b1*B}P2^{b2*B}...Pn^{bn*B}
P1b1∗BP2b2∗B...Pnbn∗B。 第三：首先，第二点是正确的，其次，若x的约数和为X，y的约数和为Y，则xy的倍数和为XY 第四：首先，第三点是正确的，其次，若pr为一个质数，易得
p
r
c
pr^c
prc的约数和=
1
+
p
r
1
+
p
r
2
+
.
.
.
+
p
r
c
1+pr^1+pr^2+...+pr^c
1+pr1+pr2+...+prc。 第五：这次没有首先了，第四点中的式子是一个等比数列，等比数列的求和公式为：
S
n
=
a
1
(
q
n
−
1
)
q
−
1
(
q
≠
1
)
S_n=\frac{a_1(q^n-1)}{q-1}(q\neq 1)
Sn=q−1a1(qn−1)(q=1) 其中a1为首项，q为等比数列公比，Sn为等比数列前n项和。
所以就可以很轻松的分解质因数+等比数列求和+乘法逆元/递归求解了！！！
代码
#include<bits/stdc++.h>
using namespace std
;
int i
,j
,k
,l
,o
,num
,ny
[9905];
long long a
[55][2],p
;
long long n
,m
;
void fjzys(long long x
)
{
long long y
=1;
num
=0;
while (y
<sqrt(x
))
{
y
++;
if (x
%y
==0)
{
num
++;
a
[num
][0]=y
;
while (x
%y
==0)
{
a
[num
][1]+=p
;
x
/=y
;
}
}
}
if (x
==1) return;
if (a
[num
][0]==x
)
{
a
[num
][1]=a
[num
][1]+p
;
}
else
{
num
++;
a
[num
][0]=x
%9901;
a
[num
][1]=p
;
}
}
long long ksm(long long w
,long long t
)
{
long long v
=1;
w
%=9901;
while (t
!=0)
{
if (t
%2==1)
{
v
=(v
*w
)%9901;
}
t
>>=1;
w
=(w
*w
)%9901;
}
return v
;
}
int main()
{
freopen("spring.in","r",stdin);
freopen("spring.out","w",stdout);
scanf("%lld %lld",&n
,&m
);
p
=m
;
fjzys(n
);
ny
[0]=0;
for (i
=1;i
<=9901;i
++)
{
ny
[i
]=ksm(i
,9899);
}
long long ans
=1;
for (i
=1;i
<=num
;i
++)
{
ans
=ans
*((ksm(a
[i
][0],a
[i
][1]+1)+9900)%9901)%9901*ny
[(a
[i
][0]+9900)%9901]%9901;
}
printf("%lld",ans
);
}
