提高级数学专题记录

__CrossBow_EXE__ · 2025-08-09 19:21:45 · 个人记录

数论分块

以 O(\sqrt n) 的复杂度求出 \left \lfloor \frac{n}{1}\right \rfloor +\left \lfloor \frac{n}{2}\right \rfloor+\left \lfloor \frac{n}{3}\right \rfloor+\dots+\left \lfloor \frac{n}{n}\right \rfloor 的值。

for(int l=1,r=0;l<=n;l=r+1){
    r=n/(n/l);
    ans+=1ll*(r-l+1)*(n/l);
}

矩阵

不细说。

struct matrix{
    int n,m;
    ll a[105][105];
}; 
il matrix operator+(const matrix &x,const matrix &y){
    matrix ans;
    if(x.n!=y.n||x.m!=y.m){
        DEBUG;
        exit(0);
    }
    ans=x;
    up(i,1,ans.n){
        up(j,1,ans.m){
            ans.a[i][j]+=y.a[i][j];
            ans.a[i][j]%=mod;
        }
    }
    return ans;
}
il matrix operator*(const matrix &x,const matrix &y){
    matrix ans;
    if(x.m!=y.n){
        DEBUG;
        exit(0);
    }
    ans.n=x.n;ans.m=y.m;
    up(i,1,ans.n){
        up(j,1,ans.m){
            ans.a[i][j]=0;
            up(k,1,x.m){
                ans.a[i][j]+=1ll*x.a[i][k]*y.a[k][j];
                ans.a[i][j]%=mod;
            }
        }
    }
    return ans;
}
il matrix operator^(matrix x,ll k){
    if(x.n!=x.m){
        DEBUG;
        exit(0);
    }
    matrix ans;
    ans.n=ans.m=x.n;
    up(i,1,ans.n){
        up(j,1,ans.m){
            ans.a[i][j]=(i==j);
        }
    }
    while(k){
        if(k&1) ans=ans*x;
        x=x*x;
        k>>=1;
    }
    return ans;
}

高斯消元

il bool is0(db x){
    return abs(x)<=eps;
}
il void Swap(int x,int y){
    if(x==y) return;
    up(i,1,n+1) swap(a[x][i],a[y][i]);
}
il void reduce(int x,int y){
    db val=a[x][y];
    up(i,1,n+1) a[x][i]/=val;
    up(i,1,n){
        if(i==x) continue;
         val=a[i][y];
        up(j,1,n+1) a[i][j]-=val*a[x][j];
    }
}
void Main(int cases){
    n=read();
    up(i,1,n){
        up(j,1,n+1){
            cin>>a[i][j];
        }
    }
    up(i,1,n){
        up(j,cnt+1,n){//找到一个第i列不为0的行 
            if(!is0(a[j][i])){
                Swap(j,cnt+1);
                break;
            }
        }
        if(!is0(a[cnt+1][i])){//找到了一个非零 
            reduce(cnt+1,i);
            cnt++;
        }
    }
    if(cnt==n){//唯一解 
        up(i,1,n){
            cout<<fixed<<setprecision(2)<<a[i][n+1]<<endl;
        }
    }else cout<<"No Solution"<<endl;
    return;
}