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

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條評論
主站蜘蛛池模板: 亚洲精品一二三四 | 一区二区精品久久 | 香蕉视频黄网站 | 99这里只有精品66视频 | 九天玄帝诀高清300集免费观看 | 桃花视频www| 吃奶japanesevideo| 免费一级特黄视频 | 日韩一区二区三区在线免费观看 | 亚洲欧美中日韩中文字幕 | 最新国产在线 | 99热热久久 | 午夜视频入口 | 看久久| 亚洲精品久久久久久久777 | 国产99区 | 国内夫妇精品对白在线播放 | 免费羞羞网站 | 亚洲精品国产啊女成拍色拍 | 国产亚洲美女 | 欧美精品18xxxhd4k | 韩日精品在线 | 91久久亚洲精品一区二区 | 国产成人欧美视频在线 | 日本精品中文字幕在线不卡 | 日韩免费小视频 | 亚洲综合站| 国产真实一区二区三区 | 国产高清一区二区三区 | www.色94色.com| 老子影院无码午夜伦不卡 | 久久久久欧美精品 | 国产深夜福利视频在线观看 | 亚洲成人在线免费视频 | 中文字幕中韩乱码亚洲大片 | 狠狠操天天操视频 | 免费综合网 | 久久久精品国产免费观看同学 | 成人看的午夜免费毛片 | 91不卡 | 成年女人在线观看 |