[POJ1845]Sumdiv

分析

对 a 分解质因数:

于是 a 的因数和表示为

括号里是一个等比数列,公比为 . 考虑递归求解等比数列

代码

#include<cstdio>
#define int long long
using namespace std;
const int N=1000,P=9901;
int a,b;
int p[N],c[N],cnt;
void divd(int x){for(int i=2;i*i<=x;i++){if(x%i)continue;
        p[++cnt]=i;
        while(x%i==0)c[cnt]++,x/=i;
    }
    if(x>1)p[++cnt]=x,c[cnt]=1;
}
int ksm(int pi,int ci){
    int res=1;
    while(ci){if(ci&1)res=res*pi%P;
        pi=pi*pi%P,ci>>=1;
    }
    return res;
}
int f(int pi,int ci){if(ci==0)return 1;
    if(ci==1)return (pi+1)%P;
    if(ci%2)return f(pi,ci/2)*(1+ksm(pi,ci/2+1))%P;
    else return ((f(pi,ci/2-1)*(1+ksm(pi,ci/2))%P)*pi+1)%P;
}
signed main(){scanf("%lld%lld",&a,&b);
    divd(a);
    int ans=1;
    for(int i=1;i<=cnt;i++){ans=ans*f(p[i]%P,c[i]*b)%P;
    }
    printf("%lld",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [POJ1845]Sumdiv

 上一篇
[SDOI2009]HH 的项链 [SDOI2009]HH 的项链
题意静态查询区间不同的数的个数 分析对询问按右端点排序 对于每个元素,更新它最后出现的位置,然后区间求个数 树状数组维护即可 复杂度 . 代码#include<cstdio> #include<al
2018.11.29
下一篇 
[AHOI2009] 中国象棋 [AHOI2009] 中国象棋
分析计数 DP 三进制状压 DP 可以拿 50 分 考虑到我们并不需要记录每一列的相对位置 定义 表示前 行中有 列放了 1 个棋子, 列放 2 个棋子的方方案数 采用刷表法,对于 $f[i,j,
2018.11.18
  目录