亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

bzoj 1951 lucas crt 費馬小定理

系統 1862 0

首先假設輸入的是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
      
      .
    

?

bzoj 1951 lucas crt 費馬小定理


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 欧美区国产区 | 中文字幕欧美亚洲 | 国产91在线 | 日本 | 四虎影视在线永久免费观看 | 久久er热这里只有精品免费 | 中国美女bbbbbxxxxx | 成人在线视频观看 | 久久机热这里只有精品无需 | 成年女人视频网站免费m | 欧美性猛交99久久久久99 | 国产欧美日本亚洲精品五区 | 免费亚洲视频在线观看 | 欧美视频日韩专区午夜 | 玖玖精品在线 | 九九香蕉视频 | 91久久老司机福利精品网 | 欧美成人免费mv在线播放 | 国产一区二区在线播放 | 午夜免费福利在线 | 91极品视频在线观看 | 久久国产精品自在自线 | 精品欧美一区手机在线观看 | 天天射综合网站 | 天天操天天玩 | 看黄色免费网站 | 午夜在线成人 | 天天爽天天干天天操 | 日本亚洲成高清一区二区三区 | 欧美性xxx | 在线观看国产一区二区三区99 | 日韩中文字幕在线不卡 | 免费在线一区二区三区 | 久草视频在线免费播放 | 日本一级毛片视频网站 | 亚洲精品久久久久久久福利 | 欧美日韩在线精品成人综合网 | 久久精品一区二区三区资源网 | 中文字幕国产欧美 | 日韩欧美一二区 | 波多野野结衣1区二区 | 久久久久久久蜜桃 |