题目

题目描述

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

输入

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

输出

The only line of the output will contain S modulo 9901.

样例输入

2 3

2 3

样例输出

15

提示

$2^3 = 8.$
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

来源

Romania OI 2002

传送门

Sumdiv

题解

问题分析

刚一看到这个题，一股浓浓的数论感就扑面而来，求 $encoding="application/x-tex">A^B</annotation></semantics></math>$ 的约数和，暴力当然是不可取的，我们不妨换个角度
如果我们把 $A$ 分解质因数，表示为

$ParseError: KaTeX parse error: Double subscript at position 14: A=p_1^(c_1)_p_̲2^(c_2)_p_3^(c_\dots$

那么 $A^B$ 可表示为

则 $A^B$ 所有约数和为
$ParseError: KaTeX parse error: Double subscript at position 26: \dots^2+...+p_1^(B_c_̲1))_$

质因数分解

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAXN 50001
const int MOD=9901;
long long a,b;
long long p[MAXN],c[MAXN];
long long m;
long long ans;


long long pow(long long p,long long n){
    long long sq=1;
    while(n){
        if(n&1)sq=(sq*p)%MOD;
        n>>=1;
        p=(p*p)%MOD;
    }
    return sq;
}

bool prime(int n){
    if(n<2)return 0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)return 0;
    }
    return 1;
}

void divide(int n){
    m=0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0&&prime(i)){
            p[++m]=i,c[m]=0;
            while(n%i==0)n/=i,c[m]++;
        }
    }
    if(n>1&&prime(n))p[++m]=n,c[m]=1;
    return;
}

long long sum(long long p,long long c){
    if(c==0)return 1;
    if(c%2==0)return (sum(p,c/2-1)*(1+pow(p,c/2+1))+pow(p,c/2))%MOD;
    else return (sum(p,c/2)*(1+pow(p,c/2+1)))%MOD;
}

void work(){
    ans=1;
    for(int i=1;i<=m;i++){
        ans=(ans*sum(p[i],c[i]*b)%MOD)%MOD;
    }
}

int main(){
    cin>>a>>b;
    divide(a);
    work();
    printf("%lld",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

#define MAXN 50001

const int MOD=9901;

long long a,b;

long long p[MAXN],c[MAXN];

long long m;

long long ans;

long long pow(long long p,long long n){

long long sq=1;

while(n){

if(n&1)sq=(sq*p)%MOD;

n>>=1;

p=(p*p)%MOD;

}

return sq;

}

bool prime(int n){

if(n<2)return 0;

for(int i=2;i<=sqrt(n);i++){

if(n%i==0)return 0;

}

return 1;

}

void divide(int n){

m=0;

for(int i=2;i<=sqrt(n);i++){

if(n%i==0&&prime(i)){

p[++m]=i,c[m]=0;

while(n%i==0)n/=i,c[m]++;

}

if(n>1&&prime(n))p[++m]=n,c[m]=1;

return;

}

long long sum(long long p,long long c){

if(c==0)return 1;

if(c%2==0)return (sum(p,c/2-1)*(1+pow(p,c/2+1))+pow(p,c/2))%MOD;

else return (sum(p,c/2)*(1+pow(p,c/2+1)))%MOD;

}

void work(){

ans=1;

for(int i=1;i<=m;i++){

ans=(ans*sum(p[i],c[i]*b)%MOD)%MOD;

}

int main(){

cin>>a>>b;

divide(a);

work();

printf("%lld",ans);

return 0;

}

发送评论编辑评论

题目