头像

wjq-AKIOI




离线:14小时前


最近来访(12)
用户头像
侯竹2022
用户头像
violet_garden
用户头像
Bochi
用户头像
今天照样没AC
用户头像
xYang_a0a1
用户头像
夜寐
用户头像
1171296052
用户头像
acwing_4698

活动打卡代码 AcWing 867. 分解质因数

wjq-AKIOI
15小时前
void get_primes(int n)
{
    int m=sqrt(n);
    for(int i=2;i<=m;i++)
    {
        int cnt=0;
        while(n%i==0)
        {
            cnt++;
            n/=i;
        }
        if(cnt) cout<<i<<" "<<cnt<<endl;
    }
    if(n>1) cout<<n<<" "<<1<<endl;    //一个数的质因数分解式中最多有一个大于sqrt(n)的质数因子
}



原题链接

本题相较于 求组合数 I 在数据范围上有扩充。
所以单纯的递推$C^b_a=C_{a-1}^{b-1}+C^b_{a-1}$是过不了的
此时想到组合计算公式
$$C^b_a=\frac{a!}{b!(a-b)!}$$
为什么不能递推阶乘呢?
于是写出代码

#include <iostream>
#define LL long long

using namespace std;

const int N=1e5+10;
const int M=1e9+7;
LL jc[N];
int n,a,b;
int main()
{
    jc[0]=1;
    for(int i=1;i<=N-10;i++)
    {
        jc[i]=jc[i-1]*i%M;
    }

    cin>>n;

    while(n--)
    {
        cin>>a>>b;

        cout<<jc[a]/jc[a-b]/jc[b]<<endl;
    }

    return 0;
}

但是没过,因为c++的除法实在是太鸡肋了
那有没有什么解决办法?

逆元

定义:对于正整数 $a, n$,如果有 $ax ≡ 1~(~mod~n~)$,则称 $x$ 的最小正整数解为 $a$ 模 $n$ 的逆元。
而在此题中,模是$10^9+7$这样的超大 质数,而我们在运算过程中不断取余,保证了$”a”<10^9+7$,所以它和模一定是互质的。所以$”x”$的意义等价于$\frac{1}{a}$。
那么怎么求逆元??
由上面的推导,不免让人想到费马小定理
若$a~,p$互素且均为正整数,$p$为质数,则
$$a^{p-1}~≡~1~(~mod~p~)$$

简直完美契合!

上面同余式等价于$a*a^{p-2}~≡~1~(~mod~p~)$
发现此时$x~=~a^{p-2}~mod~p$

这还不够惊喜的吗😀

于是代码

#include <iostream>
#define LL long long

using namespace std;

const int N=1e5+10;
const int M=1e9+7;

LL jc[N],invjc[N];
int qmi(int a,int n)
{
    int res=1;

    while(n)
    {
        if(n%2) res= (LL)res*a%M;
        a= (LL)a*a%M;
        n>>=1;
    }

    return res;
}

int main()
{
    jc[0]=invjc[0]=1;
    for(int i=1;i<=N-10;i++)
    {
        jc[i]=jc[i-1]*i%M;
        invjc[i]=qmi(jc[i],M-2);
    }

    int n,a,b;
    cin>>n;

    while(n--)
    {
        cin>>a>>b;
        cout<<jc[a]*invjc[a-b]%M*invjc[b]%M<<endl;
    }

    return 0;
}

求赞!




概念引入:

整除:

整数b能被整数a整除,即$\frac{b}{a}$是一个整数,那么称为 $a~$整除$b$ 或 $b~$能被$a$整除,记作:
$$a~|~b$$

因数

对于任意整数$x$,如果存在$a~|~x$,那么称$x$是$a$的一个因数(亦称因子或约数)

最大公因数

对于整数$a,~b$,它们的最大公因数(这里设为$k$,是整数)是使得$k~|~a~并且~k~|~b$的最大数。
记为$(a,~b)$。
特别地:规定当$b=0$时$(a,~b)=(a,~0)=a$。
欧几里得算法正是求最大公因数的

余数

如果整数b不能被整数a整除,即$a \nmid b$,则一定存在整数$k,~r$,使得$b=a*k+r~~~(0<r<a)$,我们称$r$为余数。

欧几里得算法

定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

字母表示为:
$$(a,~b)~=~(b,~r)~~~~(a>b.a,b,r∈\mathbb{Z},r是a除以b的余数)$$

证明:
$a$可以表示成$a = kb + r~(不妨设a,b,k,r∈\mathbb{N^*},~~0<r<b)$
假设$d$是$a,b$的一个公约数,记作$d|a,d|b$,即$a$和$b$都可以被$d$整除。
而$r = a - kb$,两边同时除以$d,\frac{r}{d}=\frac{a}{d}-\frac{kb}{d}$,因为$d$是$a,b$最大公因数,所以等式右边是整数,所以左边也是整数,即$\frac{r}{d}$为整数,因此$d|r$
因此$d$也是$b, r$的公约数。
因$(a,b)$和$(b,r)$的公约数相等,则其最大公约数也相等,得证。




wjq-AKIOI
10天前

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double z = 1e-6;

int n;
double a[N][N];

int gauss()
{
    int r=0,c;  //r 行 c 列
    for(c=0; c<n; c++)   //枚举要消的元是第几列(题中x_{c+1})
    {
        int t=r;
        for(int i=r;i<n;i++)
        {
            if(fabs(a[i][c]) > fabs(a[t][c]))
                t=i;
        }

        if(fabs(a[t][c]) < z) continue;   //考虑精度,与a[t][c]==0一个意思 ,此时系数最大就是0,不用处理

        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);  //把绝对值最大的换到上面

        for(int i=n;i>=c;i--) a[r][i] /= a[r][c];     //把最上面(即标准)的方程做等价变形,把第c个系数(a_{r+1,c+1})变成1
        //必须要倒着变形!(上面)
        for(int i=r+1;i<n;i++)   //消掉
            if(fabs(a[i][c]) > z)  //需要消
            {
                for(int j=n;j>=c;j--) 
                    a[i][j] -= a[r][j]*a[i][c];    //那就消
            }
        r++;
    }

    if(r<n)
    {
        for(int i=r;i<n;i++)
            if(fabs(a[i][n]) > z) return 2;   //a[i][n]是"b"      情形: 0*x1 0*x2 0*x3...0*xn = b > 0 矛盾->无解 
        return 1;  //情形: 0*x1 0*x2 0*x3...0*xn = b = 0 无穷多解 
    }

    for(int i=n-1;i>=0;i--)   //回溯求解
    {
        for(int j=i+1;j<n;j++)
        {
            a[i][n] -= a[i][j]*a[j][n];
        }
    }
    return 0;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n+1;j++)
        {
            cin>>a[i][j];
        }
    }

    int R=gauss();
    if(R==0)
    {
        for(int i=0;i<n;i++)
            if(fabs(a[i][n]) < z) cout<<"0.00\n";
            else printf("%.2lf\n",a[i][n]);
    }
    else if(R==1) cout<<"Infinite group solutions";
    else cout<<"No solution";

    return 0;
}

要不写几个雷点吧!
有些地方要倒着处理
别忘了fabs!!我就是这个调了一上午艹!




wjq-AKIOI
13天前

符号解释:“$\iff$” 读作等价于,意思是符号左边可以推向右边,从右边可以推向左边
如:$3+1\iff2+2$

形如$ax^2+bx+c=0~~(a≠0)$的方程叫做一元二次方程

一元二次方程有两个解,称为两个根,一般记为$x_1,~x_2$
方程根有以下三个情况:
1.方程有两个不同的根,即$x_1 ≠ x_2$
2.方程有两个相等的根,即$x_1 = x_2$,此时称方程的根为二重实根
3.方程在实数范围内无解

一元二次方程的求解

1.公式法

$ax^2+bx+c=0~~(a≠0)$的求解公式:
$$\frac{-b±\sqrt{Δ}}{2a}$$
其中$Δ=b^2-4ac$,称为根的判别式($Δ$是希腊字母德尔塔的小写形式)
我们发现:
$Δ > 0$时,代入公式有两个结果,对应上文根的情形1
$Δ = 0$时,公式有一个结果,对应2
$Δ < 0$时,由于根号为负数,所以公式无意义,对应3
$Δ$是完全平方数时,两个根一定是有理数,否则是无理数
所以在解一元二次方程的时候,可以先看看$Δ$的取值,进而分析根

公式法的利弊:
利:无脑方便
弊:缺乏技巧

2.十字相乘

价值

十字相乘是分解因式的重要方法之一,它的价值在于确定一个一元二次方程是由哪两个一元一次方程相乘得来的,当确定下来两个因式后,方程的解不言而喻。
例如:
$$x^2+2x+1=0 \iff (x+1)(x+1)=0$$
所以$x_1=x_2=-1$
$$x^2+x-6=0 \iff (x+3)(x-2)=0$$
所以$x_1=-3,~x_2=2$
$$2x^2-5x-3=0 \iff (2x+1)(x-3)=0$$
所以$x_1=-\frac{1}{2},~x_2=3$
即当$x$使得两个因式其中一个等于$0$时就是一个根
此时$0$乘任何数等于$0$

方法

懒得敲代码,遂手画图
QQ图片20221124121042.jpg
这里有个详细图解解释
2.jpg
建议多多练习十字相乘,掌握技巧!

3.特殊值法(进阶)

顾名思义,代入特殊值
这里先给出一个命题:
若多项式$f(x)$满足$f(a)=0,~~a∈\mathbb{R}$ 则$(x-a)|f(x)$

如$x^2-3x+2=0$,发现$x=2$时方程成立
所以方程一定可以分解成$(x-2)*F(x)$的形式,其中$F(x)$是一次的
接下来,我们可以使用长除法解决

一元二次方程的几何背景

在平面直角坐标系下,一个一元二次方程图像相当于抛物线,而方程$=0$的解反映在坐标系下就是抛物线与$x$轴的交点,即$y=0$时$x$的值
图例
333.png

222.png

111.png




wjq-AKIOI
14天前

不等式的定义

一般地,用纯粹的大于号“$>$”、小于号“$<$”表示大小关系的式子,叫作不等式。用“$≠$”表示不等关系的式子也是不等式

一元一次不等式,即不等式有且仅有一个未知量,且未知量的次数是1

如 $3x+7<2x+4$ 是一个一元一次的不等式

不等式符号的意义

简单的不等式常见符号包括
“$>$”-左边表达式的值一定比右边的大
“$<$”-左边表达式的值一定比右边的小
“$\geq$”-左边表达式的值比右边的大或相等
“$\leq$”-左边表达式的值比右边的大或相等
“$≠$”-左右表达式一定不相等

不等式的性质

1.对称性:

若$x < y$, 则 $y>x$,反之亦然.

2.传递性:

若$x > y,~y > z$, 则$x > z$.

3.加法原则:

若$x > y~,~a$为任意实数或整式 ,则$x+a > y+a$.

4.乘法原则:

若$x > y~,~a > 0$,则$ax > ay$,反之亦然;
若$x > y~,~a < 0$,则$ax < ay$,反之亦然.

5.

若$x > y,~a > b$,那么$x+a > y+b$
若$x > y > 0,~a > b > 0,~~$那么$ax > by$

不等式的计算技巧

一般的操作等同于等式,但是乘或除以负数时,不等号要变方向。不能同乘0
一般解一个不等式,习惯上将未知量放到左边,常数(常量)放到右边
如:
$$ax+b < c \iff x < \frac{c-b}{a} ~~(a > 0)$$

$$ax+b < c \iff x > \frac{c-b}{a} ~~(a < 0)$$

一元一次不等式组

顾名思义,就是多个个一元一次不等式,不等式的元一致
不等式组中每个不等式都会对于未知量给出一个范围限制(前提是有意义)
对于求解不等式组,常常要先化简不等式,或者运用不等式的性质进行技巧性运算(注意是否是等价变形)

不等式组的解集是满足所有不等式的集合

理解不等式的解集,往往要借助数轴,通过画图理解
下图出自百度百科词条【不等式】
3812b31bb051f819fa9ebe2cddb44aed2e73e719.gif



活动打卡代码 AcWing 878. 线性同余方程

wjq-AKIOI
20天前
#include <iostream>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }

    int d=exgcd(b,a%b,y,x);

    y-=a/b*x;

    return d;
}

int main()
{
    int t,a,b,m,x,y;
    cin>>t;
    while(t--)
    {
        scanf("%d%d%d",&a,&b,&m);

        int d=exgcd(a,m,x,y);

        if(b % d)
            printf("impossible\n");
        else
            printf("%d\n",(long long)x*(b/d)%m);
    }

    return 0;
}


活动打卡代码 AcWing 878. 线性同余方程

wjq-AKIOI
20天前
#include <iostream>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }

    int d=exgcd(b,a%b,y,x);

    y-=a/b*x;

    return d;
}

int main()
{
    int t,a,b,m,x,y;
    cin>>t;
    while(t--)
    {
        scanf("%d%d%d",&a,&b,&m);

        int d=exgcd(a,m,x,y);

        if(b % d)
            printf("impossible\n");
        else
            printf("%d\n",(long long)x*(b/d)%m);
    }

    return 0;
}



wjq-AKIOI
20天前
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }

    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}


活动打卡代码 AcWing 826. 单链表

wjq-AKIOI
28天前
#include <iostream>
using namespace std;

const int N=100010;
int e[N],ne[N],head=-1,idx=1;

void add_to_head()
{
    int x;
    cin>>x;
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

void del()
{
    int k;
    cin>>k;
    if(k==0)
    {
        head=ne[head];
    }
    else
    {
        ne[k]=ne[ne[k]];
    }
}

void insert()
{
    int k,x;
    cin>>k>>x;
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

int main()
{
    char c; int n;
    cin>>n;
    while(n--)
    {
        cin>>c;
        if(c=='H') add_to_head();
        if(c=='D') del();
        if(c=='I') insert();
    }
    for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
    return 0;
}