数论中的基本算法 POJ 1845 SPOJ DIVSUM

扩展欧几里得求逆元（只要a与b互素，那么就有逆元）
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define mod 9973
typedef long long ll;
void ExGcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return ;
    }
    ExGcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
}
int main(){
    int t,T,rev,x;
    int a,b;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d %d",&a,&b);
        ExGcd(b,mod,rev,x);
        printf("%d\n",((rev*a)%mod+mod)%mod);
    }
}

O(n)打素数表

[cpp]
int pn = 0,prime[MAXN],factor[MAXN];//factor[i]为i的最小素约数
void get_prime(int n){
    int i,j;
    for(i=1;i<=n;i++)
        factor[i]=i;
    for(i=2;i<=n;i++){
        if(i==factor[i])prime[pn++]=i;
        for(j=0;j<pn && prime[j]*i<=n;j++){
            factor[i*prime[j]]=prime[j];
            if(i%prime[j]==0)
                break;
        }
    }
}

POJ 1845 二分（1+x+x^2...+x^n）求和
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define mod 9901
typedef long long ll;
const int MAXN=10000;
int a,b,k;
int p[MAXN],n[MAXN];
ll quick(ll num,ll mi){
    ll ans=1;
    while(mi){
        if(mi%2)ans=(ans*num)%mod;
        num=(num*num)%mod;
        mi/=2;
    }
    return ans%mod;
}
ll sum(ll num,ll mi){
    if(mi==0)return 1;
    if(mi%2)
        return (sum(num,mi/2)*(1+quick(num,mi/2+1)))%mod;
    return (sum(num,mi/2-1)*(1+quick(num,mi/2+1))+quick(num,mi/2))%mod;
}
void factor(int a){
    int i;
    k=0;
    for(i=2;i*i<=a;){ //sqrt(n)的复杂度分解整数
        if(a%i==0){
            p[k]=i;
            n[k]=0;
            while(a%i==0){
                n[k]++;
                a/=i;
            }
            k++;
        }
        if(i>2)i+=2;
        else i++;
    }
    if(a>1){
        p[k]=a;
        n[k]=1;
        k++;
    }
}
int main(){
    int i;
    scanf("%d %d",&a,&b);
    factor(a);
    int ans=1;
    for(i=0;i<k;i++)
        ans=(ans*(sum(p[i],n[i]*b))%mod)%mod;
    printf("%d\n",ans);
}
POJ 1845 逆元的方法
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define mod 9901
typedef long long ll;
const int MAXN=10000;
int a,b,k;
int p[MAXN],n[MAXN];

void ExGcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return ;
    }
    ExGcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
}
int reverse(int num){
    int rev,x;
    ExGcd(num,mod,rev,x);
    return rev;
}
ll quick(ll num,ll mi){
    ll ans=1;
    while(mi){
        if(mi%2)ans=(ans*num)%mod;
        num=(num*num)%mod;
        mi/=2;
    }
    return ans%mod;
}
ll sum(ll num,ll mi){
    if(num%mod==1)    //注意到这种情况不能用逆元，因为num-1与mod不互素
        return (mi+1)%mod;
    return (((quick(num,mi+1)-1+mod)%mod)*reverse((num-1)%mod)%mod+mod)%mod;
}
void factor(int a){
    int i;
    k=0;
    for(i=2;i*i<=a;){ //sqrt(n)的复杂度分解整数
        if(a%i==0){
            p[k]=i;
            n[k]=0;
            while(a%i==0){
                n[k]++;
                a/=i;
            }
          &nb

补充：软件开发 , C++ ,