山东省第七届省赛

A:水

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,A,B;
    while(~scanf("%d",&T)){
        for(int i=0;i<T;++i){
            cin>>A>>B;
            if(A%B){
                cout<<(A/B)+1<<endl;
            }else{
                cout<<(A/B)<<endl;
            }
        }
    }
    return 0;
}

B:二分(或者可以暴力,只有45个FB)结论题,用到斐波那契博弈里的一个结论:任何数都可以被拆成不同斐波那契的和,进而猜测直接从最大的小于N的FB往下找即可

我吐槽下SDUT的OJ…尼玛10^9能写成109,劳资找了大大大大大大半天错硬是不知道错哪里了艹

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=45;
int Fb[maxn],M;
int vis[maxn],has_ans;

void init(){
    Fb[0]=1;
    Fb[1]=2;
    for(int i=2;i<maxn;++i){
        Fb[i]=Fb[i-1]+Fb[i-2];
        //printf("%d\n",Fb[i]);
    }

}

void solve(int N){
    stack<int> ans;
    int mx=maxn;
    while(N!=0){
        int ind=lower_bound(Fb,Fb+mx,N)-Fb;
        if(Fb[ind]>N)ind-=1;
        N=N-Fb[ind];
        ans.push(Fb[ind]);
    }
    printf("%d=",M);
    int t=0;
    while(!ans.empty()){
        if(!t){
            printf("%d",ans.top());t++;
        }else printf("+%d",ans.top());
        ans.pop();
    }
    printf("\n");
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        has_ans=0;
        scanf("%d",&M);
        solve(M);
    }
    return 0;
}

/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 40ms
Take Memory: 196KB
Submit time: 2018-03-04 13:39:50
****************************************************/

E:简单枚举

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;

int T,N,M;
char mp[maxn][maxn];
int dist[4][2]={{1,0},{-1,0},{0,-1},{0,1}};

bool check(int x,int y){
    if(x<1 || x>M || y<1 || y>N) return false;
    return true;
}

int main(){
    scanf("%d",&T);
    while(T--){
        int ans=0;
        scanf("%d%d",&M,&N);
        for(int i=1;i<=M;++i){
            scanf("%s",mp[i]+1);
        }
        for(int i=1;i<=M;++i){
            for(int j=1;j<=N;++j){
                if(mp[i][j]=='#'){
                    for(int k=0;k<4;++k){
                        int x=i+dist[k][0],y=j+dist[k][1];
                        if(check(x,y)){
                            if(mp[x][y]=='#')continue;
                            int room=0;
                            for(int kk=0;kk<4;++kk){
                                int xx=x+dist[kk][0],yy=y+dist[kk][1];
                                if(check(xx,yy)){
                                    if(mp[xx][yy]=='#')++room;
                                }
                            }
                            if(room==1)ans++;
                        }else ++ans;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 228ms
Take Memory: 212KB
Submit time: 2018-03-04 14:46:06
****************************************************/

G:找规律,不像博弈,抱歉,会打表,但是规律想不出来,对不起

打表

#include<bits/stdc++.h>
using namespace std;

int solve(int N){
    int ans=0;
    for(int i=1;i<N;++i){
        for(int j=i;j<N-i;++j){
            int k=N-i-j;
            if((i^j^k)==0) ans++;
        }
    }
    return ans;
}

int main(){
    for(int i=1;i<=200;++i){
        printf("%d: %d\n",i,solve(i)/3);
    }
    return 0;
}

找的规律,知道规律了,直接粘的别人代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ans,pp;
    int i;
    long long int f[100];
    f[2]=1;
    f[1]=0;
    f[0]=0;
    for(i=3;i<30;i++)
        f[i]=f[i-1]*3+1;
    long long int a;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a;
        ans=0;
        if(a%2)
        {
            cout<<0<<endl;
            continue;
        }
        while(a!=0)
        {
            pp=a%2;
            if(pp)
                ans++;
            a/=2;
        }
        cout<<f[ans]<<endl;
    }
}

J:题目翻译: http://www.bubuko.com/infodetail-1612259.html 说实话,完全理解题意了基本就是水题.但对我不是.

#include<bits/stdc++.h>
using namespace std;
int T;
char str[1000];
int main(){
    cin>>T;
    while(T--){
        int N,M;
        cin>>N>>M;
        int c=0,m=0,o=0,b=0;
        getchar();
        for(int i=0;i<N;++i){
            gets(str);
            if(str[0]=='C'){
                c++;
            }else if(str[0]=='M'){
                m++;
            }else if(str[0]=='O'){
                o++;
            }else if(str[0]=='B'){
                b++;
            }
        }
        int ans=o*(2+(N-1)+m*2)+b*(2+m*2);
        if(ans>=M){
            puts("Mrghllghghllghg!");
        }else puts("Tell you a joke, the execution of Paladin.");
    }
    return 0;
}

K:水

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,maxm=5010;
int N;
stack<char> st;
int main(){
    while(~scanf("%d\n",&N)){
        char qb;
        while(N--){
            int f=0;
            do{
                do{
                    qb=getchar();
                    if(isalpha(qb)) st.push(qb);
                }while(qb!=' ' && qb!='\n');
                if(f==0)f++;
                else printf(" ");
                while(!st.empty()){
                    printf("%c",st.top());
                    st.pop();
                }
            }while(qb!='\n');
            printf("\n");
        }
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) G 斐波那契博弈

斐波那契博弈模板题,我凑…

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
set<int> st;
int FB[maxn];
int n;
inline void init(){
    FB[1]=1ll;FB[0]=1ll;
    int i;
    for(i=2;FB[i-1]<=1e9+7;++i){
        FB[i]=FB[i-1]+FB[i-2];
        st.insert(FB[i]);
    }
}

int main(){
    init();
    while(~scanf("%d",&n)){
        if(st.find(n)!=st.end()){
            cout<<"Sha"<<endl;
        }else{
            cout<<"Xian"<<endl;
        }
    }
    return 0;
}

2018全国多校算法寒假练习赛(三) D

这道题以前在lrj上见过,不过没注意.

Link

https://www.nowcoder.net/acm/contest/75/D

Type: 博弈论

题目

链接:https://www.nowcoder.net/acm/contest/75/D
来源:牛客网

小牛和小客玩石子游戏,他们用n个石子围成一圈,小牛和小客分别从其中取石子,谁先取完谁胜,每次可以从一圈中取一个或者相邻两个,每次都是小牛先取,请输出胜利者的名字(小牛获胜输出XiaoNiu,小客获胜输出XiaoKe)(1 2 3 4 取走 2 13 不算相邻)

约束

输入包括多组测试数据
每组测试数据一个n(1≤n≤1e9)

输出

每组用一行输出胜利者的名字(小牛获胜输出XiaoNiu,小客获胜输出XiaoKe)

题解

我直接说推出的结论了
很明显的是:

n=0时,先手必败,n=1,2时,先手必胜

然后我们看n>=3:

  1. n=3时很明显先手必败
  2. n=4时,无论先手者取1还是2,只需要和他取一样的即可,把当前的石子堆分成两部分,每部分有一样的石子,可以发现,该情况下先手必败(只需要和先手者操作一样即可获胜).

    然后我们可以发现只要是偶数都可以这样乱搞

  3. n=5时,无论先手者取1还是2,只需要和他取相反的即可,其余和以上一样,同样将石子堆分为两堆.

    然后我们发现只要是奇数都可以这样乱搞

Code

/**

                                                                       :;LaEaHKEEGpPXU7;,
                                                                  .:75pKH11252U252XapZgRQgD6XJscLr;,.
                                                               :LXpRgGaX521JLw1JswJJsJs22XHPPEZEGDOMMRDOa7.
                                                           .r2EDDZEpZPZP6KpHX5SXH5XXa5KwaXaSX5UJ1c77sLs2GMQQ6r                                       .
                                                        ,LpgOGpEZGZEZEpZKpHHU5wP5HEDgpXpHa2SSa5aSXULr7rrirrJXRBp;                                   ;B
                                                     ,J6MRZH6EgEEZE6E6EZZPZXXwSSGQXr::aPpP5USUHaHaKa5Lvrr7ri;rLHBB2:                                Kc
                                                   rpQDOpPPOGGZOGOZG6GEOEOEDPPGBa.  .PaSSUXSUUUaUSaKXKS177r7rrrirSBBR7                             .O,
                                                :UBQOKPK6ZOOOEDEO6GZE6EpEpDgDBR:   UBpXHa5aSaUS5SUS5XapPHJc7rrv7rr7sgBBs                           .g.
                                              ;gBMPXpO6GEOEOEOEGEOEE6EZEEDRGBB    EB5pKSXpHKaHSX552S5aUHHEX17c7vr7777s5RBS:                        .R;
                                           .sQBPXpDZOODOgODGOGgEDEOEOGgGgOOMB:   LBKKSXSHa52aaKXHXKaa5aSaaHXSJLcL7vcc777JDBBg2;.                    Qi
                                         ;2ggp2EDDOggGEDGgDDOgGGZDOOZOGg6gEBX    vBZaHUKaaUXXXSXXKXpXHXH5wwaa52U1wssLsLJccv1UDQBQ67.                O7
                                       :ZZUU5PROOEOZOZGGOODZOGgODZOOgOggRgRB; ;:..R6XaKKpP6PGppKPHpHpPX5aU21UUa5Sw52UwUJJv77L77sSpQMDU;            ;B5
                                     ,SRJ7sSHGggEOZOEG6OODpOZgggOQQBBBBBQBBQ.,;;. LBOgOgDRDDZODMgQRgRDaa552a252UUa25w5UaU2sLvccs7r7sJZBBMr       ,XQJ:
                                    LQHr77J6RGOZDZOEGEDGgDRORQBBBQRDPU1Jscwa7.,::.:J7r;::::.  ..,:;i7UOgRRRgDPH5SUSU52U2HHa1JJJLJLccLr71RBB,    7R2,
                                  :RZv;77JSgGOZEODEDGOEggQBBBMS7;:,:,,.,.,.:7L;:,;.:  ,: . .....       .:;rJU6GgGRggEZHPaKXX2S221Js1Lc7r:7QB. .XX:
                                 7g1;;7rcXG6gpGDZGgZOOQBBQpr.   ::::;:;:::Jr::sr;::;:.:vs,:::::::::::,,         ,:7L5HGOggRgZUUU5wSUaJLc7r7BOiDr  ...
                               .XX;;;irLHGKpZZZEKgDRBBB6i    ,;;:;;;;r;;:s177:,;L7:;7:.rHi,:::::::::::::::::,.         .,;7ZRQgO6KUUJsLwsJ7KBM. .....
                               JZ:;rrrc5EPHp6XgpRBBBE;     :i:;;;;;:;;;:c7::r7;,::::::::rv:,:::::::::::,:,:,:,,,,            .;sORQRGX21wsXU:  .... .
                              .Br;iir72EHPHZ6EgBBR7.   ..;ii:;;;;;;;;;:71r::.:7,  .::7;:;H;.::,:::::::,:::::,,,::,,,              ,7wEDRZBMr  .......
                              1D;:r;rwOPXPKH6BBX,   .:;:;;;:::;:;;;;;::Ls,;ss..r.  ,c77;sLU,:,:::,:::,:,:,:,,,:,,,:::.                  .:.rP:.......
                              D2:i;rJpKHXHXgg7    .,,::::;:::::;:;:;;:;SL7sS2, :.   ::::,:U7.:::,:::,:,,,,,:,,.,,,.,:,                    ;L:. .. ...
                             :Qc;i7LGZPa6gBM,  ...,,::::::::::::;;::;.JJ;ic:         ;:::,v1,.:::;7,,,:,:,:,,,,.:,,,,..                :2wr.  .......
                             sRr:rrwZGgBQR7.  .,,::::::::::::::;::;:::Hr:7i          ,;;:::U: .,,,:r.,,:,:,:,,,:,,,.....             7K2:. ..........
                             OX:irsXgQZ:.   .,,:::,,:::,::::::::;;;::r5;r7:           :;;;:7L ..,.,;:,:,:,,,:,:,,,,......        .rU6w;..............
                            .BJ71EK5;.   .,,::,:,:,,,:,:,::::::::;:;.Ls;r7             :;:::s, ..,,,r:.:.,,,.:, .,..... .    .;s5XJr,..,.............
                            1Mv::.     .:,:,,,,,,,:::::::,;:::;:;::..J7;c:          ,. ,rri:27  , .,:;. ,:,:,,:..,....    .rpPL;:.. ... .............
                       ..7Ls:        .,,,:,,,:,:,:::,:,:::::,:::::: .Srrr,  .,:;;;::::..:7r;r1    .: :E:..,,:,...,,.., ..XBQ7, ................... ..
                  ,;7v7r7:,         ,,,,:.,,,,,,:,,::,:,,.::.,:.,:, :Jrr; ,r7,:..        ,:::L:  .  .7RJ .,.:.,......,,:MBs   ..............,........
            .:;vJs7i,              ,,,., ..,,:,,,:,,,:,:.,rs,,.:,,  ;J;c,                .,::;;     Lr.E: .,...,....:,:1Z:  .........,.,...........:,.
   .;,,:r7J1wv;,.               ....,.:. .,.,,:,,,:,,::::,sS;.:::,  cLrr.     .       .,. .,..:    ;;  r5 ........,,:;s7. ....,.,.,...........,.,.,,.
   ,BBs:::                   . ........,.,,,,,.:,,,:,:,,.;s7r,,,,,  cc7;         ,.,,.      .:7rrJGMPOEL1, ..... ,,:rSr, : ,.,.,.,.,.........,,,,,. ..
     rZL.                   ....... ..,,,.,,,..,,,.,;,...7J:s: ..  .wr7,        ...    .rJpQBBBBBBBQgKP77s  ..  .,7S2,,....,....,.,.,......,,.,. .:cX2
       ;SH7,               . . . .. .,.,.,.,,,...,..r, ::Ur;7L .   .57;.           .rPBBQBBBPws:;r::::.,:P.    .;S5;,..,...,.,.,.,.... ..,,, ..,7HSJvr
          r7r;:             . ... ..........,...,.. 7L;,rS;;ivr .   1r:       .  .rZBBK7;.JL,::Jrs;.:;,:;J, .,;LDv..:.,...,.,.,.,...,.,,:,, ,7sKGwc77;
             .:7L7:,            . ,r,..,.,,,...,..:iLL  7s;r;cv:    U7.         :vi;:. .. :Er:::.Ls. . ,7::::vHEi ,:,,.,,,.,.,,,,,,::::, .:1QBKJJUsssc
                .:rvw1JsL7;,      ,;..........,.:ir :r .ELr77v:,.   Pr          ..      .  Ls    ,w.   rr.r:JPr. ::,..,,,.,,,,:,:::,:,..7XgRE52US25w1c
                      .:;7JRQpX:   ; .........,i:  .,J ;gri;7r  :   1;                     .X:    .   ,v :aK1, ,,:.,,,.,,,,:::::,;::::cOBB6K55UXUX5XUw
                           ;J,XQB7,:    . ...,:   .:7Z.7Zi7;r:   ,  v,                      :w:;,.,:::7LUsc:..:,:.:,,,,,:,:::::::,:;c5BBPS5wSUSUaUaUa2
                           J7  rEBBg..,. ..... .  ,L1PLKr:,:;r;;::, :,                       :;SXsJU1XLLr....:,,,,,,::::,::::::,::LL,,rZXUJU25552aUUUU
                           JL .:sXBB:... ., .    ,OH777;,rZRBBBQL ..r,                     ,:r7::r:,;;....:,,,,,,,,.::::;::;:::.7gL    UK2UUS1aw2wU25J
                           U7 .r71BB;  . :.. .. :QJ;.;1pBBBBBGRBRi  i:                   .      .w7.   ..,,:,,,,,:,:,:::::::,.,2BR:   .DSaUSUUS525w5U1
                           2r :7rJBQ7   .;. .   KL::JGBBBgE6Hp6XMQ;     .                    ... ,2s    ,,,,:::::,:::::::,,.:sQQB2    ;DHa5U52S2U25USJ
                           a: :7;1BB2   .v,    sL;LPQgDBPH6KPQBpGBG    .                   ... ..  aP:. .. ,::,:::::,,,,.;rSgBQDa;    :gSSwSUUU525US2U
                           5; ;;r2QBB,  .s:  :a7:PBZ2,:BEaZPKgBZOgB,                        .   ...:LEHri::,:.,,.,,,::rsXRBgGKEJi,    2GH252SUS5S11wH5
                           U: ;:rwDBBr  .c, rB6r 167.,,RQPpEP6OpKEBc      .,                 .   : ::sS7;cKB6HHa1XOQRRQBRgEZDBH; ..  ;RZUPSSU525USSpK2
                           s; ;::aBg,   .; .Gv,H::,,::,;BQDOGHPXpKBs      .,.                 . .,.  .r:;:6gOEBQRRRDggQgOHgMGL,    .;PEHHXaaKaPXPKPaXS
                           s7.:,sBa     :..S,  vE::::;  7BBMgZH6pQBr             .             ,:,   ,.,r2RHSSpMZPKRRZpgggav,    ;UpEZaaaKHHUHPPaUJHGO
                           a;.775:    .::rU.    gR:,:.   :;:BBBBQar                         .  ,,   ,.,7rggJwU6DDGMgOGgXc:,   ,rPGOpKSXSXSKUKHU1UHgOEP
                          1i :SZJrLXpBBMRB:  .v  Ba,.       :sv:                             .        irsBUSpEEGPPpg65r:..,;sKZDZHSX5XaHU55K2wUGMRZ6Z6
                         :K  :7asvwc2MgEQB, :gg.:iB7  .,,,:.                      ...,.   .     ..   .:iM6GEpSSXZOEs:...;spZpKKXXSX5Xa5Ja5wwKGQDEpp6OZ
                         w; ,LXLr77sLwL5aR. gRgQgaQBi ,vJwvi,.                 .;;:;7:   .   .  ,...  rRDRJUSXpgas:,.:;U66SaHa2X5aUa552X12SgQgpZpEpGOD
                         H: ;XJ;77rv7rJUaQ;rgaPgXXHBB;        . .              .ri:;;          ,: . :6QZEKHXpXXL:,::r1PKXaa2XSS5a5S5UJ22aOBgEpOppZOOgG
                         iwsJsr7rsLrrLcJ2gQGXHwa1SUHBB:  . ... .                 ..,           :   1BRKpOEGp2Jr;::rsXP1Uaa2U5a5aUa5SsSpgQRZGZEEZZOOgDg
                           ,cs5aXaP552ssLwRSHXaSS5asXBB.      . .                             .  LBBgGgZHsr;vrr;rcXpP5UUS5X5S2XS5SS1URBggpEZgDDGOGggRD
                              ,;irrs2KgQRPJJJSUXKXSHJpBM   . . .                                ZBBOUsr;:.  ,,,rHgZPUaSaUSUSSXaUPXsSBB6ZZp6EEGOOGDEggO
                                       ;BBQQZaSJ5J15SJDQ7                                    .iEBL:.  . .,:,:;SRQGZXPXXSHaS2UUSUSswQB6OZgG6pZZGODEOGDE
                                      JgUri1aGEpEpXSS5LBQ,                              .rLap2Jr     ;712OO6ZggRDZXHXpKK2211LLLc7wgBa2PODRGE6OZgDgGDGD
                                    7QB; ,Jc76DaZXOZgDPEBBX,                       :c1HEZ1c;:,.,:;cHDgQQggMZgGOZO6OEGpXsLLsJXHPOBBBc;vss5EMggZDODOgED6
                                   LZJ::iwrrr72EPgXU5OBBBBBBBp7:               .i5P6wL;,   .:LS6DMgMgZKgEOPOGGDDGEXULvLSOBBBBBQBgDQDJ5rrr7JOQQDDZGEgDD
                                   wp rR5,       .HQRX7r72RQBBBBBQBMEK6Uc7sc7cHOU:,     .:LHgOQg6ZOPZpZGGEDERZPwcr7LKDDaJr:.      rBX;;:r:ir1DBQMgRgDp
                                   7D,sw:      ,   Z.      .LgBBQBBOsJaQBBBBBBXrr.  .:rwZBBQgROgDgDOERRMgROOScrLsPP5r,             7Qs,::::::rUgRgZOG6
                                   ,Q57:r  ,:  ,r  U:         .;;   .vL7L;r:UG7.:sr;JSgQBgDEZXXUSXpHa21svr7r7s2v:.                  iQK...:,:::;LLJJws
                                    OBHs;.  :;;,v  H:             :6X;       rpL;7pSrrr7r;::,....,,:;iirrvvvr,                       :BBPs;;:,,,,::;::
                                    ::rPDEL:..7:c;7r              pK  .:      :KL.:r:..     ..:icsS5sr:,.                              JgGgBQDOSJss77r
                                         :r;:::  ,                PH r,       ,;5: ,::::;7Ls7Lc7;:                                         ,:7JP17rJUs
                                                                  .:J: :;  .,:K6BQS7:.,.,.
                                                                    :r7Ji;r7;::;;.**/
                                                                        .
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n<=2)cout<<"XiaoNiu"<<endl;
        else cout<<"XiaoKe"<<endl;
    }
    return 0;
}

数论

对于这一个知识点的学习,我大概会通过
《ACM国际大学生程序设计竞赛:知识与入门》 以及
lrj的蓝书以及《ACM/ICPC数论及应用》来学习.

素数

素数筛法

艾氏筛法(O(nloglogn))

通常使用艾氏筛法,而艾氏筛法的思想也可用于很多地方.

线性筛法

伪码表述

算法: 线性的素数筛法
输出: 一个集合S,表示1~n以内的素数集合
具体流程:

(1) 将S初始化为{2,…,n}
(2) 维护当前确定的素数的列表L,并初始化为空
(3) 对于 2 到 n 的每一个i

(3.1) 如果当前i∈S,将i加入L
(3.2) 对于L中的每一个元素p

(3.2.1) 若i×p>n,结束循环 (3.2)
(3.2.2) 将i×p移出S
(3.2.3) 如果p整除i,结束循环 (3.2)

代码(1亿数据量1s)

实锤完毕…我的电脑竟然可以存下1亿的数组…

#include<bits/stdc++.h>
#define maxn 100001000
using namespace std;

bool valid[maxn];
int prime[maxn];
/*素数筛法 O(n),对于每个素数只标记一次*/
void getPrime(int n,int &tot,int ans[maxn]){
    memset(valid,true,sizeof(valid));
    for(int i=2;i<=n;++i){
        if(valid[i]){
            tot++;
            ans[tot]=i;
        }
        for(int j=1;((j<=tot) && (i*ans[j]<=n));++j){
            valid[i*ans[j]]=false;
            if(i%ans[j]==0) break;
        }
    }
}

int main(){
    clock_t t1 = clock();
    int tot=0;
    getPrime(100000000,tot,prime);
    clock_t t2 = clock();

    cout<<tot<<endl;
    cout<<prime[5760000]<<endl;
    cout<<"总运行时间为: "<<(double)(t2-t1)/ CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}

素数估计

如果我们设Pi(x)表示不超过x的素数的个数.可以用

x/lnx对Pi(x)进行估计

不到万不得已别用,误差蛮大的

素数判定(*Miller-Rabin)

朴素的素数判定法是通过枚举从2到n^0.5内所有的整数,看他是否能整除n.时间复杂度为O(n^0.5)

此外有一个基于概率的常数时间的素数判定法

Miller-Rabin素数判定

欧几里得算法

求gcd(a,b),欧几里得的一个结论是

gcd(a,b)=gcd(b,a%b)
求得最后结果即可

gcd性质

 gcd(a,b)=gcd(b,a) (交换律)
gcd(-a,b)=gcd(a,b)
gcd(a,a)=|a|
gcd(a,0)=|a|
gcd(a,1)=1
gcd(a,b)=gcd(b, a mod b)
gcd(a,b)=gcd(b, a-b)
如果有附加的一个自然数m,
则: gcd(ma,mb)=m * gcd(a,b) (分配律)
gcd(a+mb ,b)=gcd(a,b)
如果m是a和b的最大公约数,
则: gcd(a/m ,b/m)=gcd(a,b)/m
在乘法函数中有:
gcd(ab,m)=gcd(a,m) * gcd(b,m)
两个整数的最大公约数主要有两种寻找方法:
* 两数各分解质因数,然后取出同样有的质因数乘起来
*辗转相除法(扩展版)
和最小公倍数(lcm)的关系:
gcd(a, b) * lcm(a, b) = ab
a与b有最大公约数,
两个整数的最大公因子可用于计算两数的最小公倍数,或分数化简成最简分数。
两个整数的最大公因子和最小公倍数中存在分配律:
* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
在坐标里,将点(0, 0)和(a, b)连起来,通过整数坐标的点的数目(除了(0, 0)一点之外)就是gcd(a, b)。

扩展欧几里得

扩展算法可以求出两个整数x和y,使得ax+by=gcd(a,b)。在此前提下|x|+|y|取最小值。
对此证明:
http://blog.csdn.net/qq_20200047/article/details/71159677

即可以证明a和b的最大公约数可以写成a和b的线性表示.

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL gcd(LL a,LL b){
    return b ==0?a:gcd(b,a%b);
}

//求整数x和y,使得ax+by=d,在此前提下|x|+|y|取最小值.
//即使a,b在int范围内,也可能超出int
void exgcd(LL a,LL b,LL &d,LL &x,LL &y){
    if(!b){d=a;x=1;y=0;}
    else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}

int main(){

    return 0;
}

一些性质

记(a,b)为gcd(a,b)

(a,b)=(b,a) 且

(a,b,c)=((a,b),c)=(a,(b,c))

记[a,b]为lcm(a,b)

有同上结论

(a,b)*[a,b]=ab (gcd求lcm的由来)

唯一分解定理

简单说吧,对于任意一个整数,都可以化简成素数次幂乘积的形式.

确定正整数n的正约数个数

由唯一分解定理得到的所有素数的幂可以推出约数个数
设第i个素数的幂为{ai}

count=(a1+1)*(a2+1)*(a3+1)*…*(as+1)

而这玩意也有一个玄学快速分解算法

Pollard’s Rho

因为目前题目出现的概率很低,所以延迟学习,先学其他的.

不定方程

基本概念

变量个数多于方程个数,并且只考虑整数解的方程被称之为不定方程。典型的二元一次不定式形式为ax+by=c,其中a、b、c皆为已知整数,a、b都不为0,x、y为未知数.

性质

我们清楚以上方程的形式相当于前面提到过的扩展欧几里得式.

以下我们用python中的整除 ‘//’ 代表数学记号整除

1.二元一次方程ax+by=c有解的充要条件:

(a,b)//c

并且当(a,b)//c的时候该方程等价于

(a/(a,b))*x+(b/(a,b))*y=(c/(a,b))

2.假设二元一次不定方程ax+by=c有解,并且x0、y0为方程的一组解,则他的所有解可以表示为:

x=x0-(b/(a,b))*t
y=y0+(a/(a,b))*t
t为任意整数

3.不定方程非负解
暂略

同余方程与欧拉定理

同余方程

假设m≠0.若m//(a-b)则称a同余于b模m,记为

a≡b(mod m)

证:

a=rm+d
b=km+d
a-b=(r-k)m mod m = 0

定理1

a≡b(mod m),当且仅当m//(a-b)

定理2

a≡b(mod m),当且仅当存在整数k,使得a=b+km

定理3

同余关系是等价关系,即满足以下三条:

  1. 自反性 a≡a(mod m)
  2. 对称性 a≡b(mod m),b≡a(mod m)
  3. 传递性 a≡b(mod m),b≡c(mod m),则a≡c(mod m)

剩余系

指对于一个正整数n,一个整数集合中的数mod n所得的余数域.

完全剩余系

如果一个整数集合的剩余系包含 1~n-1 所有n可能的余数,则该剩余系被称为完全剩余系,我们简记为 Zn.

比如 Z6={0,1,2,3,4,5}

缩系

指在模n意义下完全剩余系中与n互素的剩余系,简记为Zn*.

Zn的同余等价类

Zn中的每个元素都代表所有与他同余的整数,比如n=5时,Z5中的元素”3″实际上代表了3,3+5,3+10…,所有这些整数除以5的余数都是3.

我们把满足同余关系的所有整数看成一个同余等价类,比如 3,8,13,18 都属于”模5等于3″ 这个同余等价类

关于取余等式 k=a%b 的一些性质

即(a+b)%n等,Zn同于等价类意义下四则运算

加法

(a+b)%n = ((a%n)+(b%n))%n

减法

(a-b)%n = ((a%n)-(b%n)+n)%n

乘法

ab%n=(a%n)(b%n)%n

异或

(a^b)%n=((a%n)^b)%n

Zn意义下的除法(模乘法的逆、逆元)

首先说下用处,通常在大整数 a/b 时,或者 c/d*p/x…但最后结果一定是整数时,并且对ans%n,为了避免中间除法运算,我们会用逆元(刚开始学,只知道这些用途,如有缺漏,欢迎补充).

那么向下进行吧

模乘法的逆:

在某些情况下 Zn中的两个元素a和b满足 Zn意义下 ab=1,即ab≡1(mod n).比如

在 Z15 中,7*13=1

即(7*13)%15=1

在这种情况下,我们称a和b互为乘法的逆,记为 b=a(-1),a=b(-1) [-1代表上标].

这个逆的运算很像”倒数”,因为在剩余系中,模n意义下当a(-1)存在时,”除以”一个数a等价于乘以他的乘法逆a(-1),比如在 Z15 中 7(-1)=13,因此3/7=3*7(-1)=3*13=9

这时我们会产生疑问,3/7甚至不是整数,怎么可能等于9? 请注意:

1 我们是在模n意义下对除法进行运算.
2 剩余系中每个元素对应一个同余等价类, 3/7=9的实际含义是”假定有两个整数a和b,其中a/b是整数,且a和b除以15的余数分别为3和7,则a/b除以15的余数等于 9″

比如a=528,b=22就是一例

除法逆元合理性证明

设我们要求 (a / b) mod p
且 b * k ≡ 1 (mod p),即k为b的逆元

注意这里我们可以用扩展欧几里得求出是否存在k,以及k的值
即 答案为 (a * k) mod p
因为 b * k ≡ 1 (mod p)
则有 b * k = p* x+1
得到 k = (p * x + 1) / b
将 k 代入(a * k) mod p

得到:
(a * (p * x + 1) / b) mod p
=((a * p * x) / b + a / b) mod p
=[((a * p * x) / b) mod p +(a / b)] mod p
=[(p * ((a * x) / b)) mod p +(a / b)] mod p
=(0 + (a / b)) mod p
= (a/b) mod p

定理4

若a,b,c是整数,m是正整数,且 a≡b(mod m) ,则

(1) a+c ≡ b+c(mod m)
(2) a-c ≡ b-c(mod m)
(3) ac ≡ bc(mod m)

定理5

设a,b,c,d为整数,m为正整数,若a≡b(mod m),c≡d(mod m)则(注: 一下定理两边值不一定相等,只是mod m相等):

(1) ax+cy≡bx+dy(mod m) 其中x,y为任意整数,即同余式可以相加
(2) ac≡bd(mod m) 即同余式可以相乘
(3) a^n≡b^n(mod m) 由上面那个可以推得,n>0
(4) f(a)≡f(b)(mod m) 其中f(x)为任一整数系数多项式

定理6

设a,b,c,d为整数,m为正整数,则

(1) 若 a≡b(mod m),且d//m,则a≡b(mod d)
(2) 若 a≡b(mod m),则gcd(a,m)≡gcd(b,m)
(3) a≡b(mod mi)(1<=i<=n)同时成立,当且仅当 a≡b(mod[m1,m2,m3…mn])

定理7

若ac≡bc(mod m),且gcd(c,m)=d,则a≡b(mod m/d)

证:

记 c=dc1,m=dm1,其中c1,m1互素

由 ac≡bc(mod m)
得 m//(ac-bc)
即 dm1//d(a-b)c1
故 m1//(a-b)c1
由下面那个整除的性质,因为 m1,c1 互质
则 m1//(a-b)
得 a≡b(mod m1)
即 a≡b(mod m/d)

整除的性质

若m | nk, 且m与k互素, 则m | n

欧拉函数

以前写过一次:
连接: http://be-sunshine.cn/index.php/2017/11/25/aoj-ntl_1_d-eulers-phi-function/

HDU 1849

【Nim博弈】
这道题一开始看上去不像Nim博弈,但它为什么会是Nim博弈呢?
首先我们可以看原题上的那个图:

原题说我们需要将每个格子内的棋子进行移动,当所有棋子都位于最左边编号为0的格子时,游戏结束.

首先我们将棋盘竖起来(自己画的,所以会少一点,但大体意思一样).

然后我们将其中的棋子分开来:

这样我们就可以将其转化为Nim博弈了.我们可以视为当前棋子所在的位置代表当前堆的石子个数.因为只能向左移动,即只能减少石子的数量.当棋子移动到0时,即代表石子已取空.

Code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int K;
    while(~scanf("%d",&K)){
        if(K==0) break;
        int ans=0;
        while(K--){
            int a;
            scanf("%d",&a);
            ans^=a;
        }
        if(ans==0)puts("Grass Win!");
        else puts("Rabbit Win!");
    }
    return 0;
}

HDU 1847

【博弈论 – SG函数】

题目:

Good Luck in CET-4 Everybody!

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11483 Accepted Submission(s): 7446

大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。当然,作为在考场浸润了十几载的当代大学生,Kiki和Cici更懂得考前的放松,所谓“张弛有道”就是这个意思。这不,Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”?“双扣”?“红五”?还是“斗地主”?
当然都不是!那多俗啊~
作为计算机学院的学生,Kiki和Cici打牌的时候可没忘记专业,她们打牌的规则是这样的:
1、 总共n张牌;
2、 双方轮流抓牌;
3、 每人每次抓牌的个数只能是2的幂次(即:1,2,4,8,16…)
4、 抓完牌,胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设,哪有不聪明的学生~),并且每次都是Kiki先抓牌,请问谁能赢呢?
当然,打牌无论谁赢都问题不大,重要的是马上到来的CET-4能有好的状态。

Good luck in CET-4 everybody!

Input

输入数据包含多个测试用例,每个测试用例占一行,包含一个整数n(1<=n<=1000)。

Output

如果Kiki能赢的话,请输出“Kiki”,否则请输出“Cici”,每个实例的输出占一行。

SampleInput

1
3

SampleOutput

Kiki
Cici

题解

首先我们要知道SG函数代表的是当前状态的数值.如果是0,则为先手必败(SG函数值为可到达状态中未出现的最小的整数).然后我们从SG函数延伸一下–

1.我们假设当n=0时,先手必败.
2.当n=1时,因为S(0)=0,所以当前状态是非奇异局势.先手必胜,即,你可以通过拿走一定的牌使下一个拿牌的人的局势变成奇异局势(必败态).
即转移给下一个抽牌者状态为S(0).
3.当n=2是,因为S(0)=0,S(1)=1.所以当前状态是非奇异局势,先手必胜.
即你可以把下一个抽牌者状态转换成S(0).
4.当n=3时,可到达状态为S(3-1)=S(2)=1.S(3-2)=S(1)=1.因为无论往那个状态走,都会使对方先手必胜,所以该局势为奇异局势.先手必败.

故我们可以根据以上推理过程将全部的1000个状态是否必胜预处理处来.其预处理过程为检查可以到达的状态是否存在奇异局势,如果存在,则该局势为非奇异局势,即先手必胜态.

因为可拿牌数都是2^n.所以预处理复杂度为O(nlg(n)).

PS…:其实预处理完以后你会发现.每当n%3==0时,为奇异局势.

Code:

//SG函数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

bool game[1001];

void init(){
    memset(game,false,sizeof(game));
    for(int i=1;i<=1000;++i){
        int t=1;
        while(i-t>=0){
            //如果i-t是奇异局势,则先手必胜
            if(!game[i-t]){
                game[i]=true;
                break;
            }
            t<<=1;
        }
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n)){
        if(game[n]){
            printf("Kiki\n");
        }else{
            printf("Cici\n");
        }
    }
    return 0;
}

POJ 1067

【威佐夫博弈】

//威佐夫博弈
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int k=max(n,m)-min(n,m);
        int ak=k*(1+sqrt(5))/2;
        int bk=ak+k;
        if(min(n,m)==ak&&max(n,m)==bk){
            printf("0\n");
        }else{
            printf("1\n");
        }
    }
    return 0;
}

HDU 1846

裸的巴什博奕,这道题出现了一个问题就是,我想~scanf(“%d”,&T),结果一直是wrong,所以如果是单纯用T的题还是不要这样写了.

//巴什博奕
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if((n)%(m+1)==0) printf("second\n");
        else printf("first\n");
    }
    return 0;
}

HDU 2149

【巴什博奕】

题目:

虽然不想,但是现实总归是现实,Lele始终没有逃过退学的命运,因为他没有拿到奖学金。现在等待他的,就是像FarmJohn一样的农田生涯。

要种田得有田才行,Lele听说街上正在举行一场别开生面的拍卖会,拍卖的物品正好就是一块20亩的田地。于是,Lele带上他的全部积蓄,冲往拍卖会。

后来发现,整个拍卖会只有Lele和他的死对头Yueyue。

通过打听,Lele知道这场拍卖的规则是这样的:刚开始底价为0,两个人轮流开始加价,不过每次加价的幅度要在1~N之间,当价格大于或等于田地的成本价 M 时,主办方就把这块田地卖给这次叫价的人。

Lele和Yueyue虽然考试不行,但是对拍卖却十分精通,而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。

由于Lele字典序比Yueyue靠前,所以每次都是由Lele先开始加价,请问,第一次加价的时候,
Lele要出多少才能保证自己买得到这块地呢?

Input:

本题目包含多组测试,请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数M和N(含义见题目描述,0<N,M<1100)

Output:

对于每组数据,在一行里按递增的顺序输出Lele第一次可以加的价。两个数据之间用空格隔开。
如果Lele在第一次无论如何出价都无法买到这块土地,就输出”none”。

Sample Input:

4 2
3 2
3 5

Sample Output:

1
none
3 4 5

题解

我们知道,在巴士博弈中,n=0为先手必输态,之后n=m+1为下一个先手必输态.
而当Lele在竞拍的时候,如果他所在的初始状态是如上所述的这样一个奇异局势(即先手必输局势),那他一定输(none).
当Lele在竞拍处于非奇异局势时,在选择最优的情况下,他一定可以赢得竞拍.即他只需要通过增价将对手置于奇异状态即可.
所以当我们想要找出Lele第一次出家的可能性时,只需要先找出Lele的第一个置对方为奇异局势的 价格 .然后在寻找下一个的时候只需要依次++,直到下一次加价会给对方一个 非奇异局势前 结束循环.
当然,存在一种可能性就是,初次加价可能会溢出n的价格范围.

//巴什博奕
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        if(n%(m+1)==0) printf("none\n");
        else{
            int next=0;
            while(1){
                next++;
                if((n-next)%(m+1)==0){
                    printf("%d",next);
                    break;
                }
            }
            while(next<m){
                next++;
                if((n-next)%(m+1)==0 || next>=n){
                    printf(" %d",next);
                }else{
                    break;
                }
            }
            printf("\n");
        }
    }
    return 0;
}

HDU 2188

【巴什博奕】

可以将题意转换为: 有n块石子,每次最多取m个,Grass先取.则转换成裸巴什博奕.

//巴什博奕
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,n,m;
    while(~scanf("%d",&T)){
        while(T--){
            scanf("%d%d",&n,&m);
            if((n)%(m+1)==0) printf("Rabbit\n");
            else printf("Grass\n");
        }
    }
    return 0;
}