20200910
快速幂，树状数组
long long quick_pow(long long a,long long b){
if(b==0) return a;
else if(b%2==0){
b/=2;
return quick_pow(a,b)*quick_pow(a,b);
}
else {
b/=2;
return quick_pow(a,b)*quick_pow(a,b)*a;
}
}
long long quick_pow(long long a,long long b,long long k){
if(b==0) return 1%k;
if(b==1) return a%k;
else if(b%2==0){
b/=2;
long long c=quick_pow(a,b,k)%k;
return (c%k*c%k)%k;
}
else {
b/=2;
long long c=quick_pow(a,b,k)%k;
return (c%k*c%k*a%k)%k;
}
}
int gcd(int x,int y){
return x%y==0?y:gcd(y,x%y);
}
20200909
线段树，素数筛，素数判断，质因数分解
线段树（lazy标记）
#include <cstdio>
using namespace std;
const int N=1e5+5;
long long tree[4*N],a[N],m,n,x,y,z,d,lazy[4*N];
void pushdown(int P,int l,int r)
{
int mid=(l+r)>>1;
tree[P*2]+=(mid-l+1)*lazy[P];
lazy[P*2]+=lazy[P];
tree[P*2+1]+=(r-mid)*lazy[P];
lazy[P*2+1]+=lazy[P];
lazy[P]=0;
}
void buildtree(int P,/*编号*/int l,/*左*/int r/*右*/)//对于节点编号P两个子节点编为P*2，P*2+1
{
if(l==r) {tree[P]=a[l]; return ;}
int mid=(l+r)/2;
buildtree(P*2,l,mid);
buildtree(P*2+1,mid+1,r);
tree[P]=tree[P*2]+tree[P*2+1];
}
void modifytree(int P,int l,int r,int ll,int rr,int x)//ll到rr加上x ;ll
r为被修改区间的左右端点
{
if(l==ll&&r==rr) {tree[P]+=x*(r-l+1);lazy[P]+=x;/*lazy标记*/ return;}
pushdown(P,l,r);
int mid=(l+r)/2;
if(ll>mid) modifytree(P*2+1,mid+1,r,ll,rr,x);
else if(mid>=rr) modifytree(P*2,l,mid,ll,rr,x);
else modifytree(P*2,l,mid,ll,mid,x),modifytree(P*2+1,mid+1,r,mid+1,rr,x);
tree[P]=tree[P*2]+tree[P*2+1];
}
long long asktree/*询问*/(int P,int l,int r,int askl,int askr)
//在编号为P,范围是l到r的线段中，找到askl到askr这一段
{
int mid=(l+r)/2;
if(l==askl && r==askr) return tree[P];
if(lazy[P]!=0) {
pushdown(P,l,r);}//ATTENTION
if(mid>=askr) return asktree(P*2,l,mid,askl,askr) ;
else if(mid<askl) return asktree(P*2+1,mid+1,r,askl,askr);
return asktree(P*2,l,mid,askl,mid)+asktree(P*2+1,mid+1,r,mid+1,askr);
}
int main()
{
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
buildtree(1,1,n);
//scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%lld",&x);
if(x==1) scanf("%lld %lld %lld",&y,&z,&d),modifytree(1,1,n,y,z,d);
if(x==2) scanf("%lld %lld",&y,&z),printf("%lld
",asktree(1,1,n,y,z));
}
return 0;
}
素数
1.素数筛法
(O(n))
#define maxn 1000010
bool prime[maxn];
int primes[maxn]
int num_prime=0;
void make_prime(){
prime[0]=prime[1]=false;
for(int i=2;i<=N;i++){
if(prime[i]){
primes[num_prime++]=i;
}
for(int j=0;j<num_prime &&i*primes[j]<N;j++){
prime[i*primes[j]]=false;
if(!(i%primes[j])){
break;
}
}
}
return ;
}
2.素数判断
bool check(int n){
int i;
for(int i=2;i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}
3.质因数分解
考虑到若(i)满足(n\% i=0)，则有(n\% dfrac{n}{i}=0)，所以可以仅枚举(i)从2到(sqrt{n})
时间复杂度(O(sqrt{n}))
void decom(int n){
int i;
vector<int> res;
for(i=2;i*i<=n;i++){
while(n%i==0){
res.push_back(i);
n/=i;
}
}
for(i=0;i<res.size()-1;i++) printf("%d*",res[i]);
printf("%d
",res.back());
}
如果事先已经用素数的线性筛法得到素数表了，那么有更快的方法进行质因数分解。
素数的线性筛法中国每一个合数n仅仅在i枚举到n除以n最小的素因子时被筛出，因此可以得到每一个合数最小的质因数。
对于要分解的合数n，先查表找到它最小的质因数，将其除掉，再找剩余的商种最小的质因数，依次操作，完成对n的分解。
这个过程仅仅需要(O(log n))
20200908
逆元、KMP
逆元
代码：
inv[1]=1;
for(int i=1;i<=n;i++){
inv[i]=(p-p/i)*inv[p%i]%p;
}
前缀数组与( ext{KMP})
求前缀数组代码find
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int pi[10005];
void find(char s[]){
int len=strlen(s);
for(int i=1;i<=len;i++){
int j=pi[i-1];
while(j>0 && s[i]!=s[j]) j=pi[j-1];
if(s[i]==s[j]) j++;
pi[i]=j;
}
return ;
}
char sl[10005];
int main()
{
scanf("%s",sl);
int len1=strlen(sl);
find(sl);
for(int i=0;i<len1;i++){
printf("%d ",pi[i]);
}
return 0;
}
( ext{KMP})代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define maxn 1000010
int kmp[maxn];
int la,lb,j;
char a[maxn],b[maxn];
int main(){
scanf("%s %s",a+1,b+1);
la=strlen(a+1);
lb=strlen(b+1);
for(int i=2;i<=lb;i++){
while(j&&b[i]!=b[j+1]) j=kmp[j];
if (b[j+1]==b[i]) j++;
kmp[i]=j;
}
j=0;
for(int i=1;i<=la;i++){
while(j>0&&b[j+1]!=a[i]) j=kmp[j];
if(b[j+1]==a[i]) j++;
if(j==lb) {
printf("%d
",i-lb+1);j=kmp[j];
}
}
for(int i=1;i<=lb;i++){
printf("%d ",kmp[i]);
}
return 0;
}
20200907
扩展gcd
【同余方程】
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
void exgcd1(long long a,long long b,long long &x,long long &y){
if(!b){
x=1;y=0;return ;
}
exgcd1(b,a%b,x,y);
int temp=x;
temp=x;
x=y;
y=temp-(a/b)*y;
return;
}
long long a,b,d,x,y;
int main(){
scanf("%lld %lld",&a,&b);
exgcd1(a,b,x,y);
printf("%lld",(x%b+b)%b);
return 0;
}
重载运算符
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
struct node{
int len;
int num[1005];
friend node operator *(node a,int b){
for(int i=1;i<=a.len;i++){
a.num[i]*=b;
}
for(int i=1;i<=a.len;i++){
if(a.num[i]>=10){
a.len=max(a.len,i+1);
a.num[i+1]+=a.num[i]/10;
a.num[i]%=10;
}
}
return a;
}
friend node operator +(node a,node b){
int lena=max(a.len,b.len);
for(int i=1;i<=lena;i++){
a.num[i]+=b.num[i];
}
for(int i=1;i<=lena;i++){
if(a.num[i]>=10){
lena=max(lena,i+1);
a.num[i+1]+=a.num[i]/10;
a.num[i]%=10;
}
}
a.len=lena;
return a;
}
void print(){
for(int i=len;i>=1;i--){
printf("%d",num[i]);
}
}
}tot,jie;
int temp;
int main(){
scanf("%d",&N);
tot.len=jie.len=1;
jie.num[1]=1;
for(int i=1;i<=N;i++){
jie=jie*i;
tot=tot+jie;
}
tot.print();
return 0;
}