C++知识点总结(56)：数学专题

一、进制转换类

1. 模板

1.1 十转 $x$

while(n){
    num[++idx]=num2digit(x%i);
    x/=i;
}

1.2 $x$ 转十

for(int i=s.size()-1;i>=0;i--){
    if(isdigt(s[i]))num=(num*10)+(s[i]-'0');
    else num=(num*10)+(10+s[i]-'A');
}

2. 例题

给定一个数 $n$（$1\le n\le 10^{18}$），求 $2\sim 16$ 进制下该数是否为一个上升数（每位都满足 $a_i\le a_{i-1}$）。输出若干行，每行两个空格隔开的数，第一个数是对应进制，第二个数是对应进制下的上升数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main(){
    cin>>n;
    for(int i=2;i<=16;i++){//遍历每个进制
        int num[55]={},idx=0,flag=0,x=n;
        //计算i进制下的n，存储到num[]中
        while(x){
            num[++idx]=x%i;
            x/=i;
        }
        //判断是否为上升数
        for(int i=idx-1;i>=1;i--)
            if(num[i]<num[i+1]){
                flag=1;
                break;
            }
        if(flag)continue;
        //按要求输出
        cout<<i<<" ";
        for(int i=idx;i>=1;i--)
            if(num[i]<10)cout<<num[i];
            else cout<<(char)('A'+(num[i]-10));
        cout<<endl;
    }
    return 0;
}

二、公式推导类

1. 一元二次方程解

已知：
$$a{x}^2+bx+c=0$$
则：
$$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$
推导过程：

等式两边都 $÷a$，得：
$$x^2+\frac{b}{a}x+\frac{c}{a}=0$$
移项，得：
$$x^2+\frac{b}{a}x=－\frac{c}{a}$$
方程两边都加上一次项系数 $\frac{b}{a}$ 的一半的平方，即方程两边都加上 $\frac{b^2}{4a^2}$，（配方）得
$$x^2+\frac{b}{a}x+\frac{b^2}{4a^2}=\frac{b^2}{4a^2}－\frac{c}{a}$$
$$\begin{gathered} (x+\frac{b}{2a}{)}^2=\frac{b^2-4ac}{4a^2} \\ x+\frac{b}{2a}=\pm \frac{\sqrt{b^2-4ac}}{2a} \\ x=\frac{-b\pm \sqrt{b^2-4ac}}{2a} \end{gathered}$$

2. 例题

2.1 【模板】怪物同笼

有 $n$ 组数据，给出第 $1$ 种怪物有 $a$ 个头 $b$ 条腿，第 $2$ 种怪物有 $c$ 个头 $d$ 条腿。所有怪物加起来有 $e$ 个头 $f$ 条腿。

思路：我们可以得出如下方程组（$x$ 为怪物 $1$ 的数量，$y$ 为怪物 $2$ 的数量）：
$$\{\begin{array}{l}ax+cy=e\\ bx+dy=f\end{array}$$
因此我们就推导得出 $x$ 的求解公式：
$$\begin{gathered} adx+cdy-bcx+cdy \\ (ad-bc)x=de-cf \\ x=\frac{de-cf}{ad-bc} \end{gathered}$$
以及 $y$ 的求解公式：
$$\begin{gathered} abx+ady-abx+bcy \\ (ad-bc)y=af-be \\ y=\frac{af-be}{ad-bc} \end{gathered}$$

$\text{AC}$ 代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,a,b,c,d,e,f;
signed main(){
    cin>>t;
    while(t--){
        cin>>a>>b>>c>>d>>e>>f;
        int g=d*e-c*f;
        int h=a*d-b*c;
        int i=a*f-b*e;
        int j=a*d-b*c;
        if(g%h!=0||i%j!=0||g/h<0||i/j<0){
            printf("No Solution\n");
            continue;
        }
        printf("%d %d\n",(d*e-c*f)/(a*d-b*c),(a*f-b*e)/(a*d-b*c));
    }
    return 0;
}

2.2 $K$ 的倍数

给定一个长度为 $n$ 的序列 $a$，求 $a_i-a_j\mathrm{mod}k=0$ 的个数（$1\le i<j\le n$）。

暴力枚举（ $“$差缀和$”$ ）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,cnt;
int a[200010];
int c[200010];
int s[200010];
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>=2){
            c[i]=a[i]-a[i-1];
            s[i]=s[i-1]+c[i];
        }
    }
    for(int l=2;l<=n;l++)
        for(int r=l;r<=n;r++)
            if((s[r]-s[l-1])%k==0)
                cnt++;
    cout<<cnt;
    return 0;
}

优化（同余思想）：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXK=1e5+8;
int n,k,ans;
int cnt[MAXK];//存储j之前mod k=0,1,2,...,k-1的数分别有几个
signed main(){
    cin>>n>>k;
    for(int j=1,aj;j<=n;j++){
        cin>>aj;
        ans+=cnt[aj%k]++;
    }
    cout<<ans;
    return 0;
}

三、枚举

例题

1. 二次方程

记 $s(n)$ 为正整数 $n$ 的数码和，给出 $a,b,c$，求出所有满足$$n=a\times [s(n){]}^2+b\times s(n)+c$$的正整数 $n$。

经典 $\text{G}$ 法：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int s(int n){
    int ret=0;
    while(n){
        ret+=n%10;
        n/=10;
    }
    return ret;
}
signed main(){
    cin>>a>>b>>c;
    for(int i=1;i<=1e7;i++)
        if(a*s(i)*s(i)+b*s(i)+c==i)
            cout<<i<<" ";
    return 0;
}

优化方法：
思想：反向枚举
$n$ 的范围很大（不超过 $9223372036854775807$，我就粗略地说 $10^{20}$ 了）。但是 $s(n)$ 最大也就 $9\times 20=180$。因此我们可以枚举 $s(n)$，从 $1\sim 180$，通过 $n=a\times [s(n){]}^2+b\times s(n)+c$ 算出 $n$，再通过 $sn=S(n)$ 进行验算。$\text{AC}$ 代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int s(int n){
    int ret=0;
    while(n){
        ret+=n%10;
        n/=10;
    }
    return ret;
}
signed main(){
    cin>>a>>b>>c;
    for(int sn=1;sn<=180;sn++){
        int n=a*sn*sn+b*sn+c;
        if(sn==s(n))cout<<n<<" ";
    }
    return 0;
}

2. 【模板】立方体体积

有一个立方体，它的长、宽、高是 $a,b,c$，立方体的体积等于长、宽、高的乘积。现在只知道立方体的体积等于 $n$，问立方体有多少种不同的可能的形状？长、宽、高顺序不同视作不同形状。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
signed main(){
    cin>>n;
    for(int a=1;a*a*a<=n;a++){//不妨令a<=b<=c
        if(n%a!=0)continue;
        for(int b=a;b*b<=n/a;b++){
            int c=n/a/b;
            if(a*b*c==n){
                if(a==b&&b==c)ans++;
                else if(a==b||b==c)ans+=3;
                else ans+=6;
            }
        }
    }
    cout<<ans;
    return 0;
}

3. 街头篮球

教练想要从他带领的 $n$ 名选手中选出一支篮球队。
每名选手的能力为整数，第 $i$ 名选手的能力为 $a_i$。篮球队的队员数量必须是 $3$ 人，一支队伍的总能力就是所有队员能力的总和。教练比较迷信，他的幸运数字是 $m$，所以他要求队伍的总能力必须是 $m$ 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
int cnt[1005];
int cal(int x,int y,int z){
    if(x==y&&y==z)
        return 1ll*cnt[x]*(cnt[x]-1)*(cnt[x]-2)/6;
    if(x==y)
        return 1ll*cnt[x]*(cnt[x]-1)/2*cnt[z];
    if(y==z)
        return 1ll*cnt[x]*cnt[y]*(cnt[y]-1)/2;
    return 1ll*cnt[x]*cnt[y]*cnt[z];
}
signed main(){
    cin>>n>>m;
    for(int i=1,a;i<=n;i++){
        cin>>a;
        cnt[a%m]++;
    }
    for(int i=0;i<m;i++)
        for(int j=i;j<m;j++){
            int k=(2*m-i-j)%m;
            if(j<=k)ans+=cal(i,j,k);
        }
    cout<<ans;
    return 0;
}

原文地址：https://blog.csdn.net/joe_g12345/article/details/143648606

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！