蝶恋花·春景
花褪残红青杏小。燕子飞时,绿水人家绕。枝上柳绵吹又少。天涯何处无芳草!
墙里秋千墙外道。墙外行人,墙里佳人笑。笑渐不闻声渐悄。多情却被无情恼。
（本词是伤春之作，写春景清新秀丽。同时，景中又有情理，我们仍用何处无芳草（知音）以自慰自勉。苏轼的多情却被无情恼，也不仅仅局限于对佳人的相思。）
题目传送门（内部题28）
输入格式
两个非负整数$A,B$。
输出格式
仅一个正整数，表示答案。
样例
样例输入：
2 3
样例输出：
15
数据范围与提示
样例解释：
$2^3=8$，而$8$的因子有$1,2,4,8$，而$1+2+4+8=15$。
数据范围：
$A\leqslant {10}^{12},B\leqslant {10}^{12}$。
题解
见到数学题就是化式子（弃掉）。
$A^B=p_1^{k_1}\times p_2^{k_2}\time ...\times p_n^{k_n}$
$ans=(1+p_1+p_1^2+...+p_n^{k_1})(1+p_2+p_2^2+...+p_n^{k_2})...(1+p_n+p_n^2+...+p_n^{k_n})$
之后我们发现，可以直接用等比数列求和公式$S_n=a_1\times \dfrac{1-q^n}{1-q}$即可。
时间复杂度：$\Theta(\log^2 n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
long long A,B;
long long pri[50],cnt[50],wzc[50];
long long qpow(long long x,long long y)
{
long long res=1;
while(y)
{
if(y&1)res=res*x%9901;
x=x*x%9901;
y>>=1;
}
return res;
}
void pre_work()
{
long long sqr=sqrt(A);
for(int i=2;i<=sqr&&A^1;i++)
{
if(A%i)continue;
pri[++pri[0]]=i;
while(!(A%i))
{
A/=i;
cnt[pri[0]]+=B;
}
}
if(A^1)
{
pri[++pri[0]]=A;
cnt[pri[0]]=B;
}
}
int main()
{
scanf("%lld%lld",&A,&B);
pre_work();
for(int i=1;i<=pri[0];i++)
wzc[i]=(((qpow(pri[i]%9901,cnt[i]+1)-pri[i])%9901+9901)*qpow((pri[i]-1)%9901,9899)+1)%9901;
wzc[0]=1;
for(int i=1;i<=pri[0];i++)
wzc[0]=wzc[0]*wzc[i]%9901;
printf("%lld",wzc[0]);
return 0;
}
rp++
转播
