noip-c++

C++noip数论gcd与lcm#includealgorithmusingnamespacestd;inta=12,b=20;intmain(){cout__gcd(a,b)endl;//求gcd位于algorithm库注意加两个下划线couta/__gcd(a,b)*bendl;//求lcm注意先除再乘防止溢出}1234567扩展欧几里得#includeiostreamusingnamespacestd;voidexgcd(inta,intb,int&d,int&x,int&y){if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}intmain(){intx,y,d,a,b;a=6,b=15;exgcd(a,b,d,x,y);coutx''y;}12345678910111213素数//素数判断s1单个s2筛表intn;boolvis[10000000],flag;bools1(intn){intm=sqrt(n+0.5);for(inti=2;i=m;i++)if(!vis[i]){if(!(n%i))return0;for(intj=i*i;j=n;j+=i)vis[j]=1;}return1;}voids2(intn){intm=sqrt(n+0.5);memset(vis,0,sizeof(vis));for(inti=2;i=m;i++)if(!vis[i])for(intj=i*i;j=n;j+=i)vis[j]=1;}intmain(){cinn;couts1(n);s2(n);for(inti=1;i=n;i++)if(!vis[i])couti'';}123456789101112131415161718192021222324素数埃氏筛法intm=sqrt(n+0.5);memset(vis,0,sizeod(vis);for(inti=2;i=m;i++)if(!vis[i])for(intj=i*i;j=n;j+=i)vis[j]=1;1234快速幂intpow(inta,intb,intp){intans=1;//a%=k;for(;b;b=1,a=a*a,a%=p){if(b&1)ans=ans*a;ans%=p;}returnans;}intmain(){inta,b,p;cinabp;coutpow(a,b,p);return0;}12345678910111213141516171819排列组合排列STL中有排列算法。头文件为algorithmnext_permutation(序列第一项的地址,序列最后一项的地址+1)：产生下一排列。prev_permutation(序列第一项的地址,序列最后一项的地址+1)：产生上一排列。组合intC[1001][1001];//根据实际需要开数组，必要时采用高精度类型memset(C,0,sizeof(C));for(inti=0;i=n;i++){C[i][0]=1;for(intj=0;j=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];}