Test - 4 20260306

Test - 4

A [CSP-J 2023] 小苹果

题解

scanf("%d",&n); 
while(n)
{
    cnt++;
    if(n%3==1&&!ans) ans=cnt;
    n=n-(n+2)/3;
}
printf("%d %d\n",cnt,ans);

B [CSP-J 2023] 公路

贪心，思路见 题解

没有必要用链表，代码可以更简洁一些：

int pos=1,sum=0;
for(int i=1;i<=n;i++)
{
    if(a[i]<a[pos]||i==n)
    {
        if(sum>0) 
        {
            int temp=(sum/d)+(sum%d!=0);
            ans+=(LL)temp*a[pos];
            sum=sum-(LL)temp*d; 
        }
        pos=i;
    }
    sum+=v[i];
}
printf("%lld\n",ans);

记得开 long long ！！！

C [CSP-J 2023] 一元二次方程

数论 大模拟

部分分的解法放在后面再说，先讲满分做法。

前置数论相关知识（具体内容见文章末尾）：

1. 辗转相除法 求最大公因数
2. 质数筛：普通筛法、埃式筛、欧拉筛
3. 质因数分解：算术唯一分解定理

Tips: 质数筛 和 质因数分解 用来化简根号形式，但也可以不用这两个内容，枚举完全平方数 也可以化简

直接根据题意模拟，按照 \(\Delta=b^2-4ac\) 进行分类讨论：

1. \(\Delta<0\)：无解，输出 NO

2. \(\Delta=0\)：只有一个根 \(x=-\frac{b}{2a}\)，一定是一个有理数，按照题意输出

3. \(\Delta>0\)：有两根 \(x_1=\frac{-b-\sqrt{\Delta}}{2a},x_2=\frac{-b+\sqrt{\Delta}}{2a}\)，输出其中的较大值

   这里的输出就比较复杂一些了，先把 \(\sqrt{\Delta}\) 化为最简形式

   记 \(temp=\sqrt{\Delta}\) （还未化简时的 \(\Delta\)），化简后 \(\Delta=\Delta/(temp^2)\)，\(x=\frac{-b\pm temp\sqrt{\Delta}}{2a}\)

   • 如果化简后 \(\Delta=1\)，也就是没有根号项了，两根分别为 \(x_1=\frac{-b-temp}{2a},x_2=\frac{-b+temp}{2a}\)，按照有理数输出方法其中较大的那个即可。（注意：这时的最大值不一定为 \(x_2\)，需要根据 \(a\) 的正负判断）

   • 如果化简后 \(\Delta\neq 1\)，根号项依然存在，最大值为 \(x=-\frac{b}{2a}+|\frac{temp\sqrt{\Delta}}{2a}|\)。

     先输出 \(-\frac{b}{2a}\)，这也是一个有理数。然后按照题意输出 \(|\frac{temp\sqrt{\Delta}}{2a}|\) 即可。

该过程代码如下：

scanf("%d%d",&T,&m);
F_prime();
while(T--)
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int delta=b*b-4*a*c;
    if(delta<0) printf("NO");
    else if(delta==0) print1(-b,2*a);
    else
    {
        int temp=check(delta); 
        delta/=temp*temp;
        if(delta==1) 
        {
            if(2*a<0) print1(min(-b+temp,-b-temp),2*a);
            else print1(max(-b+temp,-b-temp),2*a);
        }
        else
        {
            if(b) print1(-b,2*a), printf("+");
            print2(temp,delta,2*a);
        }
    }
    puts("");
} 

辗转相除法 找 \(p,q\) 的最大公因数：

int exgcd(int x,int y)
{
	while(y)
	{
		int res=x%y;
		x=y;
		y=res;
	}
	return x;
}

埃式筛 找 \([1,5\times m^2]\) 之间的质数（这是 \(\Delta\) 的取值范围），然后用 \(prime\) 数组从小到大存下来：

vector<int> prime;
bool vis[M];
void F_prime()
{
	vis[0]=vis[1]=true;
	for(int i=2;i<=5*m;i++)
	{
		if(vis[i]) continue;
		for(int j=i*i;j<=5*m;j+=i)
			vis[j]=true;
	}
	for(int i=1;i<=5*m;i++)
		if(!vis[i]) prime.push_back(i);
}

质因数分解 求 \(temp\)：

int check(int x)
{
	int res=1;
	for(int &p:prime)
	{
		int cnt=0;
		while(x%p==0)
		{
			x/=p;
			cnt++;
		}
		
		cnt/=2;
		for(int i=1;i<=cnt;i++)
			res*=p;
	}
	return res;
}

有理数输出：

void print1(int p,int q)
{
	if((p<0&&q>0)||(p>0&&q<0)) printf("-"); //先判断答案正负
	p=abs(p),q=abs(q);
	int gcd=exgcd(p,q);
	p/=gcd; q/=gcd; 
	if(q==1) printf("%d",p);
	else printf("%d/%d",p,q);
}

无理数输出（有根号的那一部分）：

void print2(int p,int r,int q)
{
	p=abs(p),q=abs(q);
	int gcd=exgcd(p,q);
	p/=gcd; q/=gcd;
	if(p==1&&q==1) printf("sqrt(%d)",r);
	else if(p==1) printf("sqrt(%d)/%d",r,q);
	else if(q==1) printf("%d*sqrt(%d)",p,r);
	else printf("%d*sqrt(%d)/%d",p,r,q);
}

恭喜你已经 \(\text{AC}\) 了！！！

下面来看部分分的做法：

• 特殊性质 A：

当 \(b=0\) 时，方程退化为 \(ax^2 + c = 0\)。根据求根公式，前面的有理数部分 \(q_1 = \frac{-b}{2a} = 0\)。

这意味着在输出最终结果时，永远不可能出现 q1+q2*sqrt(r) 这种两项相加的格式。

结果要么是 \(0\)（当 \(c=0\) 时），要么是纯有理数（如果 \(\Delta\) 是完全平方数），要么是纯无理数部分。

在这个性质下，我们依然需要用到线性筛素数来化简根号，但可以省去 main 函数中拼接 + 号的逻辑。

• 特殊性质 B：

当 \(c=0\) 时，\(\Delta = b^2 - 4ac = b^2\)。 因为 \(b^2 \ge 0\) 永远成立，所以 方程一定有实数解（不会输出 NO）。

\(\sqrt{\Delta} = |b|\)，这意味着 方程的解一定是两个有理数（\(0\) 和 \(-\frac{b}{a}\)），绝对不可能出现带根号（无理数）的情况。

因此，我们 不需要 线性筛素数（F_prime）、化简根号（check）以及输出无理数（print2）的函数。

• 特殊性质 C：

由于方程的实数解一定是有理数，说明如果 \(\Delta \ge 0\)，那么 \(\Delta\) 必定是一个完全平方数

这不仅意味着永远不需要调用 print2 输出根号，更意味着 不需要质因数分解来化简根号。

遇到正数 \(\Delta\)，直接调用系统自带的 sqrt() 函数开根号即可得到一个整数。

这是最简单的一个性质，只用到 exgcd 和 print1 两个函数。

D [CSP-J 2023] 旅游巴士

最短路 + 动态规划

直接输出 \(-1\)，\(5\) 分！！！

先说正解，题解 讲的很清楚，代码也很简洁 (❤ ω ❤)

然后看特殊性质：

• 特殊性质 1：\(a_i = 0\)

\(a_i = 0\) 意味着 所有道路从一开始就是开放的，不存在任何“等待开门”的时间。

既然不需要等待，每走一条边耗时严格为 \(1\)，图的边权就退化成了恒定的 \(1\)。

在这种情况下，我们 使用最基础的 BFS 和 普通的队列（queue）即可解决，状态还是 \(dis[N][M]\)。

• 特殊性质 \(2\)： \(k = 1\)

\(k = 1\) 意味着班车的发车间隔为 1，那么 任何时刻到达终点都是 1 的倍数，都符合离开的条件。

我们不再需要记录 \(dis\) 的第二维，\(dis[N][M]\) 可以降维成一维数组 \(dis[N]\)。

同时，如果当前时间小于道路开放时间 \(a_i\)，我们可以在起点等 \(a[i]-t\) 就行了，一定是 \(k\) 的倍数。

• 特殊性质 3：\(u_i \leq v_i\)

\(u_i \leq v_i\) 意味着所有的边都是从编号小的点指向编号大的点。

整个图是一个 有向无环图 (DAG)，并且点的编号本身就已经是一个 拓扑序！

直接按照编号的顺序做 dp 就行了。

void dp()
{
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k;j++)
			dis[i][j]=INF;
	dis[1][0]=0;
	
	for(int x=1;x<=n;x++)
	{
		for(int j=0;j<k;j++)
		{
			if(dis[x][j]==INF) continue;
			int t=dis[x][j];
			for(int i=head[x];i!=-1;i=Edge[i].nxt)
			{
				int y=Edge[i].y, val=Edge[i].val;
				if(t<val)
				{
					if(dis[y][(t+1)%k]>dis[x][t%k]+(val-t+k-1)/k*k+1)
						dis[y][(t+1)%k]=dis[x][t%k]+(val-t+k-1)/k*k+1;
				}
				else
				{
					if(dis[y][(t+1)%k]>dis[x][t%k])
						dis[y][(t+1)%k]=dis[x][t%k]+1;
				}			
			}
		}
	}
} 

补充数论知识：质数和约数

一、整除与约数

设 \(n\) 为非负整数， \(d\) 为正整数，若 \(\cfrac{n}{d}\) 为整数，则称 \(d\) 整除 \(n\)，记为 \(d|n\) 。

此时，则称 \(d\) 是 \(n\) 的约数，或因数、因子；\(n\) 为 \(d\) 的倍数。

二、质数的判定——试除法 \(O(\sqrt n)\)

bool F_prime(int x)
{
    if(x<2) return false;
    int n=sqrt(x);
    for(int i=1;i<=n;i++)
        if(x%i==0) return false;
    return true;
}

三、质数筛法

筛法一 \(O(\sum_{i=1}^n\frac{n}{i}) = O(n \log n)\)

void F_prime() //vis[i]:1为合数，0为质数
{
    memset(vis,0,sizeof(vis));
    vis[0]=vis[1]=1; //特殊处理0和1
    for(int i=2;i<=n;i++)
        for(int j=i*2;j<=n;j+=i)
            vis[j]=1;
}

筛法二——埃氏筛 \(O(\sum_{质数 \ p\leq n} = O(n \log \log n))\)

“筛法一” 中有些合数被重复标记了多次

Example: \(12\) 在枚举 \(2,3,4,6\) 的倍数中都被重复标记了

仔细观察，发现只需要枚举质数的倍数就可以标记到所有的合数

对于每个质数 \(p\)，小于 \(p^2\) 的 \(p\) 的倍数在扫描到更小的质数的时候就已经被标记了

因此，得到以下筛法：

从 \(2\) 到 \(n\) 枚举整数 \(i\)，若 \(i\) 是质数，则把 \(i^2,(i+1)\times i\sim \lfloor\cfrac{n}{i}\rfloor\times i\) 标记为合数，枚举到 \(i\) 时，若 \(i\) 未被标记，则 \(i\) 为质数。

void F_prime()
{
    memset(vis,0,sizeof(vis));
    vis[0]=vis[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(vis[i]) continue;
        for(int j=i*i;j<=n;j+=i)
            vis[j]=1;
    }
}

时间效率接近线性，是算法竞赛中常用的质数筛法。

筛法三——欧拉筛 \(O(n)\)

经埃氏筛优化后，仍会存在合数被重复标记

Example: \(12\) 在枚举 \(2,3\) 的倍数的过程中都被标记了

其根本原因是因为没有确定出唯一产生 \(12\) 的方式

因此设数组 \(v\) 记录每个数的最小质因子，按以下步骤维护 \(v\)：

1. 从 \(2\) 到 \(n\) 枚举整数
2. 若 \(v[i]=i\)，则 \(i\) 为质数
3. 扫描不大于 \(v[i]\) 的每个质数 \(p\)，令 \(v[i*p]=p\)，因为 \(p\leq v[i]\)，所以 \(p\) 为合数 \(i*p\) 的质因子，每个合数 \(i*p\) 只会被他的最小质因子筛一次

void F_prime()
{
    memset(v,0,sizeof(v)); //v[i]表示i的最小质因数为v[i]
    m=0; //m表示质数的数量。
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0) //i是质数
            v[i]=i,prime[++m]=i;
        //给当前的数i乘上一个质因子
        for(int j=1;j<=m;j++)
        {
            //v[i]有比prime[j]更小的质因子(比如v[i]也是i*prime[j]的质因子而且比prime[j]小)
            //或者超出n的范围停止循环
            if(prime[j]>v[i]||prime[j]>n/i)  break;
            v[i*prime[j]]=prime[j];
        }
    }
}

输出：

for(int i=1;i<=n;i++)
   printf("%d\n",prime[i]);

Example: 区间筛质数

有 \(t\) 组询问，每组询问给出两个正整数 \(a\) 和 \(b\)，输出 \(a \sim b\) 之间所有质数

\(1 \leq t \leq 100 , \ 1 \leq a < b \leq 10^{12} , \ b - a \leq 10^6\)

因为 \(b\) 以内的合数的最小质因子一定不超过 \(\sqrt b\)

因此可以筛出 \(2\sim \sqrt b\) 以内的质数

与此同时将这些质数在 \(a\sim b\) 的范围内所有的倍数全部标记

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int l,r;
bool prime[N],prime_small[50010];
void found_prime()
{
	for(int i=1;i*i<=r;i++)
		prime_small[i]=1;
	prime_small[1]=0;
	int t=sqrt(r);
	for(int i=l;i<=r;i++) prime[i-l]=1;
	for(int i=2;i<=t;i++)
	{
		if(prime_small[i])
		{
			for(int j=i*i;j<=t;j+=i)
				prime_small[j]=0;
			for(int j=max(2,(l+i-1)/i)*i;j<=r;j+=i)
				prime[j-l]=0;
		}
	}	
}

四、\(gcd\) 与 \(lcm\)

\(gcd(a,b)\) 表示 \(a,b\) 的最大公因数，\(lcm(a,b)\) 表示 \(a,b\) 的最小公倍数。

\(gcd\) 的性质：

1. \(gcd(a,b)=gcd(b,a)\)

2. 若 \(gcd(a,b)=1\)，则 \(a，b\) 互质;

3. 任何正整数都是 \(0\) 和 \(0\) 的公约数，故 \(gcd(0,0)\) 不存在

4. \(gcd(c,a)=a \times gcd(a,0)=a\)

5. 若 \(k\) 为整数，\(gcd(k\times a,k\times b)=k\times gcd(a,b)\)

\(lcm\) 的性质：

由定义得 \(lcm(a,b)=\cfrac{a\times b}{gcd(a,b)}\)

更相减损术

设 \(a,b\) 为正整数且 \(a\geq b\)，则有 \(gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)\)。

证明：

对于 \(a,b\) 的任意公约数 \(d\)，都有 \(a=k_1\times d,b=k_2\times d\)

则 \(a-b=(k_1-k_2)\times d\)，因此 \(d\) 也是 \(b,a-b\) 的公约数

故 \(a,b\) 的公约数集合与 \(b,a-b\) 的公约数集合相同

于是它们的最大公约数也是相等的

即 \(gcd(a,b)=gcd(b,a-b)\)。

同理，\(gcd(a,b)=gcd(a,a-b)\)。

辗转相除法（欧几里德算法）

设 \(a,b\) 为正整数且 \(b\neq 0\)，则有 \(gcd(a,b)=gcd(b,a\bmod b)\)。

① 若 \(a<b\)，则 \(gcd(b,a\bmod b)=gcd(b,a)=gcd(a,b)\)。

② 若 \(a\geq b\)，设 \(a=q\times b+r\)，其中 \(0\leq r\leq b\)，显然 \(r=a\bmod b\)

对于 \(a,b\) 的任意公约数 \(d\)，都有 \(a=k_1\times d,b=k_2\times d\)

则 \(r=a-q\times b=(k_1-k_2\times q)\times d\)，因此 \(d\) 也是 \(b,r\) 的公约数

故 \(a,b\) 的公约数集合与 \(b,a\bmod b\) 的公约数集合相同

于是它们的最大公约数也是相等的

即 \(gcd(a,b)=gcd(b,a \bmod b)\)。

\(gcd\) 求法 \(O(\log {(a+b)})\)

一直执行欧几里德算法直至 \(gcd(x,0)\)，此时 \(x = gcd(a,b)\)

函数写法

int gcd(int a,int b)
{
	while(b>0)
    {
        int x=a%b;
        a=b;
        b=x;
	}
    return a;
}

递归写法

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

Example: \(gcd\) 与 \(lcm\)

给出某两个整数 \(a\) 和 \(b(a \leq b)\) 的最大公约数 \(gcd\) 和最小公倍数 \(lcm\)，请找出满足的 \(a\) 和 \(b\)，使得 \(b-a\) 的值最小。

Exercise:

​ **1. Neko does Maths CF1152C Neko does Maths **

​ 2. Prime Distance UVA10140 Prime Distance

五、算数基本定理

算数基本定理又名唯一分解定理，任何一个大于 \(1\) 的正整数都能唯一分解为若干个质数的乘积。

1. 分解式

设 \(n\geq 2\) 为整数，则有唯一的分解的分解式：

\[n=p_1 ^{c_1} \times p_2 ^{c_2} \times \cdots \times = \prod _{i=1} ^m p_i ^{c_i} \]

其中 \(c_i\) 都是正整数，\(p_i\) 都是质数，且满足 \(p_1 < p_2 < \cdots <p_m\)。

​ Example: \(24=2^3 \times 3\)；\(147=3 \times 7^2\)；\(2860=2^2 \times 5 \times 11 \times 13\)。

用此定理进行质因数分解，时间复杂度为 \(O(\log n \sim \sqrt n)\)

Example: 阶乘分解

给定整数 \(N(1\leq N\leq 10^6)\)，试把阶乘 \(N!\) 分解质因数，按照算术基本定理的形式输出分解结果中的\(p_i\)和\(c_i\)即可。

2. 推论

推论一：

\(n\) 的正约数个数为：

\[(c_1+1) \times (c_2+1) \times \cdots \times (c_m+1) = \prod _{i=1} ^m (c_i+1) \]

推论二：

\(n\) 的所有正约数的和为：

\[(1 + p_1 + p_1^2 + \cdots + p_1^{c_i}) \times (1 + p_m + p_m^2 + \cdots + p_m^{c_m}) = \prod _{i=1} ^m ( \sum _{j=0} ^{c_i} (p_i)^j) \]

3. 质因数分解

对于一个大于 \(1\) 的正整数 \(n\)，有且仅有一个质因子大于 \(\sqrt n\)。

因此对于 \(n\) 进行质因数分解时，可以扫描 \(2 \sim \lfloor \sqrt n \rfloor\) 内的每个数 \(d\)，

若 \(d\) 能整除 \(n\)，则从 \(n\) 中除掉所有的因子 \(d\)，同时累计除去的 \(d\) 的个数。

时间复杂度为 \(O(\sqrt n)\)

void devide_prime(int x)
{
	m=0;
    int n=sqrt(x);
    for(int i=2;i<=n;i++)
    {
        if(n%i!=0) continue;
        p[++m]=i; c[m]=0;
        while(n%i==0)
        {
            n\=i;
            c[m]++;
		}
	}
    //原始的n是质数或者原始的n中最大的质因子大于sqrt(n)
    if(n>1) p[++m]=n,c[m]=1;
}