bzoj 1951 lucas crt 费马小定理

首先假设输入的是n,m

我们就是要求m^(Σ(c(n,i) i|n)) mod p

那么根据费马小定理，上式等于

m^(Σ(c(n,i) i|n) mod  (p-1)) mod p

那么问题的关键就是求 Σ(c(n,i) i|n) mod  (p-1)了

那么如果P是素数的话，我们可以用lucas定理来快速求出来组合数，这道题的p-1是

非素数，那么我们分解质因数pi，假设c(n,i) i|n为X，那我们求出来X mod pi=ai，这个是

符合lucas定理的，那么我们可以得到质因子数个式子（本题有4个质因子），然后我们用

中国剩余定理合并这4个式子就行了

/**************************************************************
    Problem: 1951
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:108 ms
    Memory:540 kb
****************************************************************/
 
//By BLADEVIL
const
    d39                     =999911659;
    pp                      :array[1..4] of longint=(2,3,4679,35617);
     
var
    n, m, k                 :int64;
    cc                      :int64;
    a                       :array[0..10] of int64;
    i                       :longint;
    fac                     :array[0..40000] of int64;
     
function ex_gcd(a,b:int64):int64;
var
    z                       :int64;
begin
    if b=0 then
    begin
        ex_gcd:=1;
        cc:=0;
        exit;
    end else
    begin
        z:=ex_gcd(b,a mod b);
        ex_gcd:=cc;
        cc:=z-(a div b)*cc;
    end;
end;    
 
function gcd(a,p:int64):int64;
begin
    gcd:=ex_gcd(a,p);
    gcd:=(gcd mod p+p) mod p;
end;
     
function combine(a,b,p:int64):int64;
var
    ans1, ans2              :int64;
    i                       :longint;
begin
    ans1:=fac[a] mod p;
    ans2:=(fac[a-b]*fac[b]) mod p;
    ans2:=gcd(ans2,p);
    combine:=ans1*ans2 mod p;
end;
     
function lucas(x,y,p:int64):int64;
var
    a, b                    :int64;
begin
    if y=0 then exit(1);
    a:=x mod p;
    b:=y mod p;
    if a<b then exit(0) else lucas:=lucas(x div p,y div p,p)*combine(a,b,p);
end;    
 
function crt:int64;
var
    i                       :longint;
begin
    crt:=0;
    for i:=1 to 4 do
        crt:=(crt+a[i]*((d39-1) div pp[i])*gcd((d39-1) div pp[i],pp[i])) mod (d39-1);
end;
 
function get(x:int64):int64;
var
    i, j                    :longint;
begin
        for i:=1 to trunc(sqrt(x)) do
        begin
            if x mod i=0 then
            begin
                for j:=1 to 4 do
                begin
                    a[j]:=(a[j]+lucas(x,i,pp[j])) mod pp[j];
                    if x div i<>i then a[j]:=(a[j]+lucas(x,x div i,pp[j])) mod pp[j];
                end;
            end;
        end;
    get:=crt;
end;
 
function mi(n,k,p:int64):int64;
var
    sum                     :int64;
begin
    mi:=1;
    sum:=n;
    while k<>0 do
    begin
        if k mod 2=1 then mi:=mi*sum mod p;
        sum:=sum*sum mod p;
        k:=k div 2;
    end;
end;
 
begin
    fac[0]:=1;
    for i:=1 to pp[4] do fac[i]:=fac[i-1]*int64(i) mod (d39-1);
    read(n,m);
    if m mod d39=0 then
    begin
        writeln(0);
        halt;
    end;
    k:=get(n);
    writeln(mi(m,k,d39));
end.