数论复习[试水]

~~这个肯定不好解释那我就少写一点注释吧orz~~

~~绝对不是我懒~~

0/1分数规划

题目：一中oj P1821

【复赛模拟试题】0/1分数规划[1]

描述

　　有N道题目，每道题目都有不同的分值和难度，分别为Ai和Bi。要求从中任选选K(K<=N)道题目，满足分值和与难度和的比最大。

输入

　　第一行两个整数N和K，接下来得N行，每行包含两个整数：Ai和Bi 。

输出

　　最大的分值与难度比(乘以100后四舍五入为3位小数)。

输入样例 1

输出样例 1

700.000

提示

1<=N<=100000 1<=Ai,Bi<=2000

代码

//这个也就是构造函数使其极度贴近答案
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k,a[100005],b[100005];
struct node{
    int a,b;
    double p;
}e[100005];
bool cmp(node x,node y)
{
    return x.p>y.p;
} 
double di(double r)
{
    for(int i=1;i<=n;i++)
    {
        e[i].a=a[i];
        e[i].b=b[i];
        e[i].p=a[i]-b[i]*r;
    }
    sort(e+1,e+n+1,cmp);
    int sa=0,sb=0;
    for(int i=1;i<=k;i++)
    {
        sa+=e[i].a;
        sb+=e[i].b;
    }
    return sa*1.0/sb*1.0;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }
    double ans=0,oa;
    do{
        oa=ans;
        ans=di(oa);
    }while(fabs(oa-ans)>1e-7);
    printf("%.3lf",ans*100);
    return 0;
}

矩阵乘法

回顾矩阵乘法

//C=A*B 
#include<cstdio>
using namespace std;
int a[105][105],b[105][105],n1,m1,n2,m2;
long long c[105][105];
int main()
{
    scanf("%d%d%d%d",&n1,&m1,&n2,&m2);
    if(m1!=n2)
    {
        printf("Can't do juzhen chengfa");
        return 0;
    }
    for(int i=1;i<=n1;i++)
    {
        for(int j=1;j<=m1;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n2;i++)
    {
        for(int j=1;j<=m2;j++)
        {
            scanf("%d",&b[i][j]);
        }
    }
    for(int i=1;i<=n1;i++)
    {
        for(int j=1;j<=m2;j++)
        {
            for(int k=1;k<=m1;k++)
            {
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    for(int i=1;i<=n1;i++)
    {
        for(int j=1;j<=m2;j++)
        {
            printf("%lld ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

回顾快速幂

#include<cstdio>
using namespace std;
long long qkpow(long long a,long long b,long long p)
{
    long long ans=1;
    while(b)
    {
        if(b&1)
        (ans*=a)%=p;//ans=ans*a%p
        (a*=a)%=p;//a=a*a%p
        b>>=1; //b=b/2
    }
    return ans;
}
int main()
{
    long long a,b,p;
    scanf("%lld%lld%lld",&a,&b,&p);
    printf("%lld^%lld mod %lld=%lld",a,b,p,qkpow(a,b,p));
    return 0;
}

然后合起来就是我们的矩阵快速幂(o´▽｀o)

题目：洛谷 P1962

斐波那契数列

大家都知道，斐波那契数列是满足如下性质的一个数列：

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

请你求出 f(n) mod 1000000007 的值。

输入输出格式

输入格式：

·第 1 行：一个整数 n

输出格式：

第 1 行： f(n) mod 1000000007 的值

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

说明

对于 60% 的数据： n ≤ 92

对于 100% 的数据： n在long long(INT64)范围内。

代码

#include<cstdio>
#include<cstring>
using namespace std;
int n=2,p=1000000007;
long long k;
long long a[5][5],b[5][5],c[5][5];
int main()
{
    scanf("%lld",&k);
    if(k==1||k==2)
    {
        printf("1");
        return 0;
    }
    if(k==0)
    {
        printf("0");
        return 0;
    }
    k-=3;
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    b[1][1]=1;
    b[1][2]=1;
    b[2][1]=1;
    while(k)
    {
        if(k&1)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    for(int k1=1;k1<=n;k1++)
                    {
                        c[i][j]+=a[i][k1]*b[k1][j];
                        c[i][j]%=p;
                    }
                }
            }
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                b[i][j]=c[i][j];
                c[i][j]=0;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k1=1;k1<=n;k1++)
                {
                    c[i][j]+=a[i][k1]*a[k1][j];
                    c[i][j]%=p;
                }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                a[i][j]=c[i][j];
                c[i][j]=0;
            }
        k/=2;
    }
    printf("%lld",(b[1][1]+b[2][1])%p);
    return 0;
}

高斯消元

题目：一中oj P1942

【训练题】高斯消元[1]

描述

　　贾老二是个品学兼优的好学生，但由于智商问题，算术学得不是很好，尤其是在解方程这个方面。虽然他解决 2x=2 这样的方程游刃有余，但是对于 {x+y=3 x-y=1} 这样的方程组就束手无策了。于是他要你来帮忙。前提是一次方程组且保证在integer的范围内可以处理所有问题。

输入

　　第一行一个数字N（1≤N≤100）表示要求的未知数的个数，同时也是所给的方程个数。　　第2到N+1行，每行N+1个数。前N个表示第1到N个未知数的系数。第N+1个数表示N个未知数乘以各自系数后的加和。（保证有唯一整数解）

输出

　　一行N个数，表示第1到N个未知数的值。

输入样例 1

2
1 1 3
1 1 1

输出样例 1

2 1

提示

1≤N≤100

代码

#include<bits/stdc++.h>
using namespace std;
double c[105][105];
int n;
bool jud(double x0)
{
    if(fabs(x0)>1e-8)
    return true;
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n+1;j++)
        {
            scanf("%lf",&c[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        //找到一个c[j][i]不为0的然后把其他的列c[j][i]减成0
        for(int j=i;j<=n;j++)
        {
            if(jud(c[j][i]))
            {
                if(j!=i)
                for(int k=1;k<=n+1;k++)
                {
                    double t=c[j][k];
                    c[j][k]=c[i][k];
                    c[i][k]=t;
                }
                break;
            }
        }
        for(int j=1;j<=n;j++)
        {
            if(j==i)continue;
            double r=c[j][i]/c[i][i];
            for(int k=1;k<=n+1;k++)
            {
                c[j][k]-=c[i][k]*r;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        double x1=(c[i][n+1]/c[i][i]);
        int x;
        if(x1<0)//四舍五入 
        {
            x=x1-0.5;
        }
        else
        {
            x=x1+0.5;
        }
        printf("%d ",x);
    }
    return 0;
}

乘法逆元

一中oj P3378

A/B mod C

描述

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)。

我们给定的A必能被B整除（A|B)，且gcd(B,9973) = 1。

输入

数据的第一行是一个T，表示有T组数据。每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

输出

对应每组数据输出(A/B)%9973。

输入样例 1

2
1000 53
87 123456789

输出样例 1

7922
6060

提示

0 <= n < 9973，1 <= B <= 10^9

代码

#include<cstdio>
using namespace std;
long long T,n,a,b=9973,x,y,c=1;
long long exgcd(long long a1,long long b1)
{
    if(b1==0)
    {
        x=1;
        y=0;
        return a1;
    }
    long long d=exgcd(b1,a1%b1);
    long long tx=x;
    x=y;
    y=tx-a1/b1*y;
    return d;
}
long long inv(int a)
{
    long long x0=exgcd(a,b);
    x=(x%b+b)%b;
    return x;
}
int main()
{
    scanf("%lld",&T);
    for(long long iT=1;iT<=T;iT++)
    {
        scanf("%lld%lld",&n,&a);
        printf("%lld\n",(n*(inv(a)))%9973);
    }
    return 0;
}

卡特兰数

公式

1.f(n)= $\sum_{i=0}^{n-1}$ f(i)*f(n-1-i),f(0)=1

2.f(n)= $\frac{4n-2}{n+1}$ f(n-1)

3.f(n)= $\frac{C_{2n}^n}{n+1}$

4.f(n)= $C_{2n}^n$ - $C_{2n}^{n-1}$

适用情况：入栈<=出栈的方案数

贴上以前写的总结

~~这些就没办法了，只能靠背板子吧orz~~

A. 质数

暴力判断质数

Eratosthenes筛

for(int i=2;i<=sqrt(1000000+2);i++)
{
   if(!a[i])
   {
       for(int j=i;j*i<=1000000+2;j++)
       {
           a[j*i]=1;
       }
   }
}
for(int i=2;i<=1000002;i++)
{
   if(!a[i])
   {
       b[++p]=i;
   }
}

欧拉筛

void oula()
{
  for(int i=2;i<=n;i++)
  {
      if(v[i]==0)
      {
          v[i]=i;
          p[++np]=i;
      }
      for(int j=1;j<=np&&i*p[j]<=n;j++)
      {
          if(v[i]<p[j])
          {
              break;
          }
          v[i*p[j]]=p[j];
      }
  }
}

B. 约数

求约数（暴力，筛法）

最大公约数

int gcd(int a,int b)
{
if(b==0)return a;
return gcd(b,a%b);
}

求phi(暴力，顺便a1存约数个数，a2存约数和）

long long phi(long long x)
{
long long t=x,x0=x;
long long t1=1;
for(long long i=2;i<=sqrt(x);i++)
{
   if(x%i==0)
   {
       t=t*(i-1)/i;
       int k=1;
       long long k1=1,k2=1;
       while(x%i==0)
       {
           k++;
           x=x/i;
           k1*=i;
           k2+=k1;
       }
       t1*=k2;
       a1*=k;
   }
}
if(x>1)
{
   t=t*(x-1)/x;
   t1*=(1+x);
   a1*=2;
}
a2=t1;
return t;
}

4.求phi（欧拉筛）

void oula()
{
for(int i=2;i<=n;i++)
{
   if(!ip[i])
   {
       f[i]=i-1;
       p[++np]=i;
   }
   for(int j=1;i*p[j]<=n;j++)
   {
       f[i*p[j]]=f[i]*(p[j]-1);
       ip[i*p[j]]=true;
       if(i%p[j]==0)
       {
           f[i*p[j]]=f[i]*p[j];
           break;
       }
   }
}
}

5.求phi(e筛）

void es()
{
    for(int i=1;i<=n;i++)p[i]=i;
    p[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(p[i]==i)
        {
            for(int j=1;i*j<=n;j++)
            {
                p[i*j]=p[i*j]/i*(i-1);
            }
        }
    }
}

C. 同余

求exgcd

int exgcd(int a1,int b1)
{
if(b1==0)
{
   x=1;
   y=0;
   return a1;
}
int d=exgcd(b1,a1%b1);
long long t=x,t1=a1/b1;
x=y;
y=t-t1*y;
return d;
}

2.扩展欧几里得求线性同余方程

x0=exgcd(a,b);
   if(c%x0!=0)
   {
       printf("No solution\n");
       continue;
   }
   x=c/x0*x,y=c/x0*y;
   long long k=x;
   int bx=b/x0;
   int ax=a/x0;
   if(bx<0)
   {
       bx=-bx;
       ax=-ax;
   }
   x=(x%bx+bx)%bx;
   y=y-(x-k)/bx*ax;
   if(x==0)
   {
       x+=bx;
       y-=ax;
   }
   printf("%lld %lld\n",x,y);

3.扩展中国剩余定理

for(long long i=1;i<=n;i++)
   {
       scanf("%lld",&b0[i]);
       b0[i]=b0[i]%a0[i];
       long long x1=x;
       a=m,b=a0[i],c=b0[i]-x;
       long long x0=exgcd(a,b);
       if(c%x0!=0)
       {
           N=x-1;
           break;
       }
       x=c/x0*x;
       long long k=x;
       long long bx=b/x0;
       if(bx<0)
       {
           bx=-bx;
       }
       x=(x%bx+bx)%bx;
       x=x1+x*m;
       m=m/x0;
       m*=a0[i];
       x=x%m;
   }

D. 矩阵运算

矩阵快速幂

k--;
while(k)
{
   if(k&1)
   //chen(b,a);//b=b*a%p
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           for(int k=1;k<=n;k++)
           {
               c[i][j]+=a[i][k]*b[k][j];
               c[i][j]=c[i][j]%p;
           }
       }
   }
   if(k&1)
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           b[i][j]=c[i][j];
           c[i][j]=0;
       }
   }
   //chen(a,a);//a=a*a%p
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           for(int k=1;k<=n;k++)
           {
               c[i][j]+=a[i][k]*a[k][j];
               c[i][j]=c[i][j]%p;
           }
       }
   }
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           a[i][j]=c[i][j];
           c[i][j]=0;
       }
   }
   k>>=1; //k=k/2
}

E. 高斯消元

消元规律：当某一行系数xi!=0&&xi之前为0，可以用该行消去其他行的xi
定义为double
贴代码

for(int i=1;i<=n;i++)
{
double t1=0.0;
int p=i;
for(int j=i;j<=m;j++)
{
   if(fabs(c[j][i])>1e-6)
   {
       if(fabs(t1)<fabs(c[j][i]))
       {
           p=j;
           t1=c[j][i];
       }
   }
}
if(p!=i)
{
   for(int k=1;k<=n+1;k++)
   {
       double t=c[p][k];
       c[p][k]=c[i][k];
       c[i][k]=t;
   }
}
if(fabs(c[i][i])<1e-6)continue;
for(int j=1;j<=m;j++)
{
   if(j==i)continue;   
   double r=c[j][i]/c[i][i];
   int cnt=0;
   for(int k=i;k<=n+1;k++)
   {
       c[j][k]-=c[i][k]*r;
   }
}
}

F.组合数学

求C(n,m)和A(n,m) 暴力法

int fa1(int n,int m)
{
int t=1;
for(int i=n-m+1;i<=n;i++)
{
   t*=i;
}
return t;
}
int fc1(int n,int m)
{
int t=1;
for(int i=1;i<=m;i++)
{
   t*=i;
}
return fa1(n,m)/t;
}

2.乘法逆元法（c[n]存n!）

long long exgcd(long long a1,long long b1)
{
if(b1==0)
{
   x=1;
   y=0;
   return a1;
}
long long d=exgcd(b1,a1%b1);
long long t=x,t1=a1/b1;
x=y;
y=t-t1*y;
return d;
}
long long inv(long long a)
{
x=0,y=0;
long long b=p,c=1;
long long x0=exgcd(a,b);
x=c*x/x0;
long long k=x;
long long bx=b/x0;
if(bx<0)
{
   bx=-bx;
}
x=(x%bx+bx)%bx;
return x%p;
}
long long fc(long long n,long long m)
{
return c[n]*inv(c[m])%p*inv(c[n-m])%p;
}
long long fa(long long n,long long m)
{
return c[n]*inv(c[n-m])%p;
}

3.lucas算法==>C(n,m)%p=lucas(n,m)=C(n%p,m%p)*lucas(n/p,m/p)%p

long long lu(int n,int m)
{
if(m==0)return 1;
return (fc(n%p,m%p)*lu(n/p,m/p))%p;
}

贴上自己以前的默写记录

痛苦地边推边记边默写

写个愚蠢的博客记录自己的绝望orz ~~结果发现因为换了个电脑之前默写的已经随风飘散了orz~~

1.求phi(f),最小质因子(v)，莫比乌斯(u)的默写的~~多半是错误的~~代码

#include<cstdio>
using namespace std;
int v[10005],np,p[10004],f[10005],u[10005];
bool ip[10005];
void oula()
{
    for(int i=2;i<=10000;i++)
    {
        if(!ip[i])
        {
            p[++np]=i;
            f[i]=i-1;
            u[i]=-1;
            v[i]=i;
        }
        for(int j=1;j<=np&&i*p[j]<=10000;j++)
        {
            ip[i*p[j]]=1;
            v[i*p[j]]=p[j];
            if(i%p[j]==0)
            {
                u[i*p[j]]=0;
                f[i*p[j]]=f[i]*p[j];
                break;
            }
            f[i*p[j]]=f[i]*(p[j]-1);
            u[i*p[j]]=-u[i];
        }
    }
    return;
}
int main()
{
    oula();
    return 0;
}

2.~~多半是错的~~默写的~~草率的~~快速幂

long long qkpow(int a,int k,int p)
{
    long long ans=1;
    while(k)
    {
        if(k&1)
        {
            ans*=a;
            ans%=p;
        }
        a*=a;
        a%=p;
        k/=2;
    }
    return ans;
}

3.~~大概是对的自己才想起来做的热乎的~~降幂(P3788)扩展欧拉函数

int phi(int x)
{
    int t=x;
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        {
            t=t/i*(i-1);
            while(x%i==0)
            {
                x=x/i;
            }
        }
    }
    if(x>1)
    {
        t=t/x*(x-1);
    }
    return t;
}
long long qkpow(long long a,long long b,int p)
{
    long long ans=1;
    while(b)
    {
        if(b&1)
        ans=ans*a;
        if(ans>=p)
        {
            ans%=p;
            ok=1;
        }
        a=a*a;
        if(ok)
        a%=p;
        b>>=1; //b=b/2
    }
    return ans;
}
long long f(int p,int i)
{
    if(p==1)return 0;
    if(i>n)return 0;
    int fp=phi(p);
    ok=0;
    long long ffp=f(fp,i+1);
    if(ok)
    ffp+=fp;
    return qkpow(a[i],ffp,p);
}

4.反复默写并推算多次大概可能应该或许是对的线性同余方程（我觉得这挺重要的因为这可以变形解决很多问题~~其实就是我的智商不能支持我直接背得滚瓜烂熟所以才默写这么多次orz~~）

#include<bits/stdc++.h>
using namespace std;
long long x,y;
int exgcd(int a,int b)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b);
    long long t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}
int main()
{
    int a,b,c;
    while((scanf("%d%d%d",&a,&b,&c))!=EOF)
    {
        int x0=exgcd(a,b);
        if(c%x0!=0)
        {
            printf("No solution\n");
            continue;
        }
        x=c/x0*x,y=c/x0*y;
        int ax=a/x0,bx=b/x0;
        long long tx=x;
        if(bx<0)
        {
            bx=-bx;
            ax=-ax;
        }
        x=(x%bx+bx)%bx;
        y=y-(x-tx)/bx*ax;
        if(x==0)
        {
            x+=bx;
            y-=ax;
        }
        printf("%lld %lld\n",x,y);
    }
    return 0;
}

5.~~因为oj暴毙所以完全不知道是不是对的~~默写的康托和逆康托

#include<bits/stdc++.h>
using namespace std;
int n,a[105];
vector<int>g;
bool v[105];
long long ans,c[105]={1},s;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]*i;
    }
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        int cnt=0;
        for(int j=1;j<x;j++)
        {
            if(v[j]==0)cnt++;
        }
        ans+=cnt*c[n-i];
        v[x]=1;
    }
    printf("%lld\n",ans+1);
    scanf("%lld",&s);
    s--;
    g.clear();
    for(int i=1;i<=n;i++)
    g.push_back(i);
    for(int i=1;i<=n;i++)
    {
        int cnt=s/c[n-i];
        s%=c[n-i];
        int t=1;
        t=g[cnt];
        g.erase(cnt+g.begin());
        a[i]=t;
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

~~（oj现在活过来了,我还是pac......orz)~~

6.~~艰难地~~默写出来的矩阵乘法斐波那契

#include<cstdio>
#include<cstring>
using namespace std;
int n=2,p=1000000007;
long long k;
long long a[5][5],b[5][5],c[5][5];
int main()
{
    //freopen(".txt","w",stdout);
    scanf("%lld",&k);
    if(k==1||k==2)
    {
        printf("1");
        return 0;
    }
    if(k==0)
    {
        printf("0");
        return 0;
    }
    k-=3;
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    b[1][1]=1;
    b[1][2]=1;
    b[2][1]=1;
    while(k)
    {
        if(k&1)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    for(int k1=1;k1<=n;k1++)
                    {
                        c[i][j]+=a[i][k1]*b[k1][j];
                        c[i][j]%=p;
                    }
                }
            }
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                b[i][j]=c[i][j];
                c[i][j]=0;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k1=1;k1<=n;k1++)
                {
                    c[i][j]+=a[i][k1]*a[k1][j];
                    c[i][j]%=p;
                }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                a[i][j]=c[i][j];
                c[i][j]=0;
            }
        k/=2;
    }
    printf("%lld",(b[1][1]+b[2][1])%p);
    return 0;
}

继续痛苦地复习明天就要考试了~~爆零玩家~~慌得一比

1.扩展中国剩余定理

#include<cstdio>
using namespace std;
int p;
long long x,y,m,ans;
long long T,N,n,a0[1000004],b0[1000004];
long long exgcd(long long a1,long long b1)
{
    if(b1==0)
    {
        x=1;
        y=0;
        return a1;
    }
    long long d=exgcd(b1,a1%b1);
    long long t=x,t1=a1/b1;
    x=y;
    y=t-t1*y;
    return d;
}
int main()
{
    scanf("%lld",&T);
    for(long long iT=1;iT<=T;iT++)
    {
        scanf("%lld%lld",&N,&n);
        m=1;
        x=0;
        for(long long i=1;i<=n;i++)
        {
            scanf("%lld",&a0[i]);
        }
        for(long long i=1;i<=n;i++)
        {
            scanf("%lld",&b0[i]);
            b0[i]%=a0[i];
            long long tx=x;
            long long a=m,b=a0[i],c=b0[i]-x;
            long long x0=exgcd(a,b);
            if(c%x0!=0)
            {
                x=N+1;
                break;
            }
            x=x*c/x0;
            long long bx=b/x0;
            if(bx<0)bx=-bx;
            x=(x%bx+bx)%bx;
            x=tx+x*m;
            m=m*a0[i]/x0;
            x%=m;
        }
        if(x==0)
        {
            x+=m;
        }
        if(N<x)
        {
            ans=0;
        }
        else
        {
            ans=(N-x)/m+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

2.十分粗糙的高斯消元

#include<bits/stdc++.h>
using namespace std;
int n;
double a[105][105];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n+1;j++)
    {
        scanf("%lf",&a[i][j]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(fabs(a[j][i])>1e-6)
            {
                if(j==i)break;
                for(int k=1;k<=n+1;k++)
                {
                    swap(a[i][k],a[j][k]);
                }
                break;
            }
        }
        for(int j=1;j<=n;j++)
        {
            if(j==i)continue;
            double r=a[j][i]/a[i][i];
            for(int k=1;k<=n+1;k++)
            {
                a[j][k]-=a[i][k]*r;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        double x1=(a[i][n+1]/a[i][i]);
        int x;
        if(x1<0)
        {
            x=x1-0.5;
        }
        else
        {
            x=x1+0.5;
        }
        printf("%d ",x);
    }
    return 0;
}

3.艰难默写出的莫比乌斯反演

#include<bits/stdc++.h>
using namespace std;
int T;
int u[50005],p[50005],cnt;
bool ip[50005];
int x,y,k;
long long s[50005];
void getu()
{
    u[1]=1;
    for(int i=2;i<50001;i++)
    {
        if(!ip[i])
        {
            u[i]=-1;
            p[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*p[j]<=50001;j++)
        {
            ip[i*p[j]]=1;
            if(i%p[j]==0)
            {
                u[i*p[j]]=0;
                break;
            }
            u[i*p[j]]=-u[i];
        }
    }
    for(int i=1;i<50001;i++)s[i]=s[i-1]+u[i];
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&T);
    getu();
    for(int iT=1;iT<=T;iT++)javascript:void(0);
    {
        scanf("%d%d%d",&x,&y,&k);
        if(x>y)swap(x,y);
        x/=k;
        y/=k;
        long long t=0;
        long long r;
        for(int i=1;i<=x;i=r+1)
        {
            r=min((x/(x/i)),(y/(y/i)));
            t+=(s[r]-s[i-1])*(x/i)*(y/i);
        }
        printf("%lld\n",t);
    }
    return 0;
}

数论复习[试水]

0/1分数规划

题目：一中oj P1821

【复赛模拟试题】0/1分数规划[1]

描述

输入

输出

输入样例 1

输出样例 1

提示

代码

矩阵乘法

回顾矩阵乘法

回顾快速幂

题目：洛谷 P1962

斐波那契数列

题目描述

输入输出格式

输入输出样例

说明

代码

高斯消元

题目：一中oj P1942

【训练题】高斯消元[1]

描述

输入

输出

输入样例 1

输出样例 1

提示

代码

乘法逆元

一中oj P3378

A/B mod C

描述

输入

输出

输入样例 1

输出样例 1

提示

代码

卡特兰数

公式

1.f(n)=f(i)*f(n-1-i),f(0)=1

2.f(n)=f(n-1)

3.f(n)=

4.f(n)=-

适用情况：入栈<=出栈的方案数

贴上以前写的总结

A. 质数

B. 约数

C. 同余

D. 矩阵运算

E. 高斯消元

F.组合数学

贴上自己以前的默写记录

1.f(n)= $\sum_{i=0}^{n-1}$ f(i)*f(n-1-i),f(0)=1

2.f(n)= $\frac{4n-2}{n+1}$ f(n-1)

3.f(n)= $\frac{C_{2n}^n}{n+1}$

4.f(n)= $C_{2n}^n$ - $C_{2n}^{n-1}$