题解 | #Sumdiv#

Sumdiv

https://ac.nowcoder.com/acm/problem/50922

代码

读懂代码前需要掌握的芝士:

唯一分解定理

任意正整数都有且只有一种方式写出其素因子的乘积表达式。

约数和方程

对于已经分解的整数

有A的所有因子之和为

我们先记录素因子,然后利用约数和方程求解。这里有一个二分加速的过程,推导在代码里面。
牛客上面有三道Sumdiv大家可以顺便A了。

思路

#include<iostream>
using namespace std;
const int mod=9901;
typedef long long ll;

ll A,B,k=0;
ll p[20005],n[20005];

ll fpow(ll p, ll n){ //快速幂 
    ll res=1;
    p%=mod;
    while(n){
        if(n&1) res=res*p%mod;
        p=p*p%mod;
        n>>=1;
    }
    return res;
}

ll sum(ll p, ll n){  //求约数和方程的每一项 
    //递归二分法求等比数列1+pi+pi^2+pi^3+...+pi^ni;
    //=(1+p+p^2+...+p^(n/2))*(1+p^(n/2+1)) 
    if(n==0) return 1; //只有p^0这一项 
    if(n%2){ //n为奇数
        return ((sum(p,n/2)%mod)*(1+fpow(p,n/2+1)))%mod;  
    }else{ //n为偶数
        return ((sum(p,n/2-1)%mod)*(1+fpow(p,n/2+1))%mod+fpow(p,n/2))%mod;
    }
}

signed main(){
    cin>>A>>B;
    for(int i=2;i*i<=A;){ //根号法+递归法
        if(A%i==0){ //如果i是A的因子 
            p[++k]=i; //记录所有素因子
            n[k]=0;
            while(!(A%i)){ 
                n[k]++; //记录素因子的个数 
                A/=i;
            }
        }
        if(i==2) i++; //奇偶法,2以外的偶数并非素数 
        else i+=2;  //特判:分解整数A(A为质数)  
    }
    if(A!=1){
        p[++k]=A;
        n[k]=1; 
    }
    if(!A){
        cout<<0<<endl;
        return 0;
    }
    ll ans=1; //约数和 
    for(int i=1;i<=k;i++){
        ans=(ans*(sum(p[i],n[i]*B)%mod))%mod; //约数和方程 
        //n[i]*B可能会超过int,因此用long long 
    }
    cout<<ans<<endl; //输出答案 
}

全部评论

相关推荐

02-08 15:53
门头沟学院 Java
CoderEcho:让公司知道便宜没好货
点赞 评论 收藏
分享
醒工硬件:1学校那里把xxxxx学院去了,加了学院看着就不像本校 2简历实习和项目稍微精简一下。字太多,面试官看着累 3第一个实习格式和第二个实习不一样。建议换行 4项目描述太详细了,你快把原理图贴上来了。比如可以这样描述:使用yyyy芯片,使用xx拓扑,使用pwm控制频率与占空比,进行了了mos/电感/变压器选型,实现了xx功能 建议把技术栈和你做的较为有亮点的工作归纳出来 5熟悉正反激这个是真的吗
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客企业服务