题目描述 A - Tomorrow link

In the calendar of AtCoder Kingdom, a year consists of $M$ months from month $1$ to month $M$, and each month consists of $D$ days from day $1$ to day $D$.What day follows year $y$, month $m$, day $d$ in this calendar?

Constraints

• $1000≤y≤9000$
• $1≤m≤M≤99$
• $1≤d≤D≤99$
• All input values are integers.

样例

blablabla

算法

(签到题) $O(1)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int m, d;
int ny, nm, nd;

int main(){
    cin >> m >> d;
    cin >> ny >> nm >> nd;
    nd += 1;
    if(nd > d) nd -= d, nm += 1;
    if(nm > m) nm -= m, ny += 1;
    cout << ny << ' ' << nm << ' ' << nd << endl;
    return 0;
}

题目描述 B - Buy One Carton of Milk link

A supermarket sells egg packs.
A pack of $6$ eggs costs $S$ yen, a pack of $8$ eggs costs $M$ yen, and a pack of $12$ eggs costs $L$ yen.
When you can buy any number of each pack, find the minimum amount of money required to purchase at least $N$ eggs.

Constraints

• $1≤N≤100$
• $1≤S,M,L≤10^4$
• All input values are integers.

样例

blablabla

算法1

(枚举) $O(n^3)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, s, m, l;

int main(){
    cin >> n >> s >> m >> l;
    int minAmount = 0x3f3f3f3f;
    for (int num6 = 0; num6 <= n; ++num6){
        for (int num8 = 0; num8 <= n; ++num8){
            for (int num12 = 0; num12 <= n; ++num12){
                if (num6 * 6 + num8 * 8 + num12 * 12 >= n) {
                    int amount = num6 * s + num8 * m + num12 * l;
                    minAmount = min(minAmount, amount);
                }
            }
        }
    }
    cout << minAmount << endl;
    return 0;
}

算法2

(背包) $O(n)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;

int n, s, m, l;
int v[] = {0, 6, 8, 12}, w[5];
int f[N];

int main(){
    cin >> n >> w[1] >> w[2] >> w[3];
    memset(f, 0x3f, sizeof f); 
    f[0] = 0; 
    for (int i = 1; i <= 3; i ++ )
        for (int j = 0; j <= n; j ++ )
            f[j] = min(f[j], f[max(j - v[i], 0)] + w[i]);
    cout << f[n] << endl;
    return 0;
}

题目描述 C - Sum of Numbers Greater Than Me link

You are given a sequence $A$=$(A_1,…,A_N)$ of length $N$.
For each $i$=$1,…,N,$ solve the following problem.
Problem: Find the sum of all elements in $A$ that are greater than $A_i$.

Constraints

• $1000≤y≤9000$
• $1≤m≤M≤99$
• $1≤d≤D≤99$
• All input values are integers.

样例

blablabla

算法

$(后缀和+upperbound)$ $O(nlogn)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 10;
typedef long long LL;

int n;
LL a[N], s[N], b[N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    for(int i = n; i >= 1; i -- ){
        s[i] = s[i + 1] + b[i];
    }
    for(int i = 1; i <= n; i ++ ){
        int idx = upper_bound(b + 1, b + 1 + n, a[i]) - b;
        printf("%lld ", s[idx]);
    }
    return 0;
}

题目描述 D - Tile Pattern link

There is a grid with $10^9$by $10^9$ squares. Let $(i,j)$ denote the square at the ${(i+1)}$th row from the top and the ${(j+1)}$th column from the left $(0≤i,j<10^9)$. (Note the unusual index assignment.)

Each square is $black$ or $white$. The color of the square $(i,j)$ is represented by a character P[i%N][j%N] , where ${‘B’}$ means black, and ${‘W’}$ means white. Here, $a%b$ denotes the remainder when $a$ is divided by $b$.

Answer $Q$ queries.
Each query gives you four integers $A,B,C,D$ and asks you to find the number of $black$ squares contained in the rectangular area with $(A,B)$ as the top-left corner and $(C,D)$ as the bottom-right corner.

Constraints

• $1≤N≤1000$
• $P$$[i]$$[j]$ is $W$ or $B$.
• $1≤Q≤2×10^5$
• $0≤A≤C<10^9$
• $0≤B≤D<10^9$
• $N,Q,A,B,C,D$ are all integers.

样例

Sample Input

3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5

Sample Output

4
7

算法

$(二维前缀和)$ $O(n^2)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const LL N = 1010;

LL n, q;
char p[N][N];
LL dp[N][N];
LL A, B, C, D;

LL f(LL x, LL y){
    //完整的n*n的矩形区域中的黑块数
    LL res = (x / n) * (y / n) * dp[n][n];
    //块(x, y)的与整数个区域n*n的右下角块 将区域分成了四个部分
    //如第一个样例的第一个询问:
    //(1, 1)到(3, 3)的矩形区域为区域n*n的整数倍，为左上角蓝色方框区域
    //(4, 4)到(4, 5)的区域为右下角紫色方框区域
    //(4, 1)到(4, 3)的区域为左下角粉色方框区域
    //(1, 4)到(3, 5)的区域为右上角橙色方框区域
    //这里求右下角部分的黑块数
    res += dp[x % n][y % n];
    //这里求左下角部分的黑块数
    res += dp[x % n][n] * (y / n);
    //这里求右上角部分的黑块数
    res += dp[n][y % n] * (x / n);
    return res;
}

int main(){
    scanf("%lld%lld", &n, &q);
    //相当于这里的i,j是指正方形小块的坐标，从1开始
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ ){
            cin >> p[i][j];
            dp[i][j] = (p[i][j] == 'B') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
        }
    //而下面用于询问的A,B,C,D是线交点的坐标，从0开始
    //那么实际对应的正方形小块的坐标还要在横纵方向上加1
    //而求前缀和的话,A,B就不需要加了而C,D则还要加1
    while(q -- ){
        scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
        C ++, D ++;
        printf("%lld\n", f(C, D) - f(A, D) - f(C, B) + f(A, B));
    }
    return 0;
}

题目描述 E - Set Meal link

AtCoder cafeteria sells meals consisting of a main dish and a side dish.
There are $N$ types of main dishes, called main dish 1, main dish 2, $…$, main dish N. Main dish i costs
$a_i$ yen.
There are $M$ types of side dishes, called side dish 1, side dish 2, $…$, side dish M. Side dish i costs
$b_i$yen.
A set meal is composed by choosing one main dish and one side dish. The price of a set meal is the sum of the prices of the chosen main dish and side dish.
However, for $L$ distinct pairs $(c_1,d_1),…,(c_L,d_L)$, the set meal consisting of main dish $c_i$ and side dish $d_i$ is not offered because they do not go well together.
That is, $NM−L$ set meals are offered. (The constraints guarantee that at least one set meal is offered.)

Find the price of the most expensive set meal offered.

Constraints

• $1≤N,M≤10^5$
• $0≤L≤min(10^5,NM−1)$
• $1≤a_i,b_i≤10^9$
• $1≤c_i≤N$
• $1≤d_j≤M$
• $(c_i,d_i)\not=(c_j,d_j)\ $ $if\ i\not=j$
• All input values are integers.

样例

blablabla

算法

$O(nm)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
const LL N = 1e5 + 10;
LL n, m, l;
vector<pair<LL, LL> > a, b;
map<pair<LL, LL>, LL> pr;
LL x, c, d;
LL ans;

int main(){
    scanf("%lld%lld%lld", &n, &m, &l);
    for(int i = 0; i < n; i ++ ){
        scanf("%lld", &x);
        a.push_back({x, i + 1});
    }
    for(int i = 0; i < m; i ++ ){
        scanf("%lld", &x);
        b.push_back({x, i + 1});
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for(int i = 0; i < l; i ++ ){
        scanf("%lld%lld", &c, &d);
        pr[{c,d}] = 1;
    }
    for(int i = a.size() - 1; i >= 0; i -- ){
        auto t1 = a[i];
        for(int j = b.size() - 1; j >= 0; j -- ){
            auto t2 = b[j];
            if(pr[{t1.second, t2.second}] == 1) continue;

            if(t1.first + t2.first > ans) ans = t1.first + t2.first;
            else break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

题目描述

AcWing 890. 能被整除的数

样例

1000000000 16
9091 3793 4201 7901 3557 6473 6761 3491 5381 6883 9643 9491 6869 4787 1129 8443

算法1

(套用线性筛模板，但是只用给的素数筛)

时间复杂度（不会算，但是线性筛的时间复杂度是O（n），输入的m最大才16，应该不会超时）

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int M = 20,N=1e9+7;
int primes[M];
bool st[N];
int n,m;
// 根据代码中的定义，const int N = 1e9 + 7，这意味着数组st的大小为10亿（1e9）。
// 在大多数情况下，这会导致内存限制超出。因为布尔类型通常占用1字节（8位），所以一个长度为1亿的布尔数组将占用大约800MB的内存。
//int类型是4个字节，若把st设为int将使用更大的内存！
int fun(int x){
    int cnt=0;
    for(int i=1;i<=x;i++){
        if(!st[i])cnt++;
        for(int j=0;j<m;j++){
            if((long long)primes[j]*i<=x)st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
    return n-cnt;
}
int main(){
    cin>>n>>m;
    // memset(st,false,sizeof st);  
    //这个系统测评貌似是看你用到了多大内存，而不是看你分配了多大内存，比如我开一个1e9+7的bool数组，
    //如果不加这句memset(st,false,sizeof st); 那么当输入的n足够小，是不会导致内存超限的，但是一旦加了这句，就代表我使用了1e9+7的
    //bool数组，不管输入的n多小，都会报内存超限。
    //
    for(int i=0;i<m;i++) cin>>primes[i];
    int res = fun(n);
    cout<<res;
    // 1  3 4 5 6 7 8 9 10
}

所以还是得老老实实用容斥原理

//3706
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, res = 0;
    cin >> n;
    for(int i = 0;i < 1 << n;++ i){
        bool f = 1;
        for(int j = 1;j < n; ++j){
            if(i >> j & 1 && i >> j - 1 & 1){
                f = 0;
                break;
            }
        }
        if(f) res ++;
    }
    cout << res;
    return 0;
}

657.选择练习1 题解

题目描述

读取 4个整数值 $A，B，C$和 $D$。

如果四个整数同时满足以下条件：

$B$大于$C$。
$D$大于$A$。
$C$和$D$的总和大于$A$和$B$的总和。
$C$和$D$是正值。
$A$是偶数。
则输出 Valores aceitos，否则，输出 Valores nao aceitos。

输入格式

输入占一行，包含四个整数 $A,B,C,D$
。

输出格式

如果输入数值满足题目条件则输出 Valores aceitos，否则输出 Valores nao aceitos。

数据范围

$−100≤A,B,C,D≤100$

样例

输入样例：

5 6 7 8

输出样例：

Valores nao aceitos

C++ 代码

#include <cstdio>

using namespace std;

int main() {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if (b > c && d > a && c + d > a + b && c > 0 && d > 0 && a % 2 == 0) printf("Valores aceitos\n");
    else printf("Valores nao aceitos\n");
    return 0;
}

各位帅哥美女们点个赞赞呗 求求了…

The end~~~

1.完全背包法：f[i][j]表示在不超过j的背包，能放入1到i的数字的总方案数

状态转移方程：f[i][j] = f[i-1][j] + f[i][j - i]

• 推导
  f[i][j] = f[i-1][j] + f[i-1][j - i], f[i-1][j - 2i] …
  f[i][j-i] = f[i-1][j-i] + f[i-1][j - 2i] + f[i-1][j-3i]
  f[i][j] = f[i-1][j] + f[i][j-i]

f[i-1][j]表示一个i数字都没拿，而f[i-1][j - i], f[i-1][j - 2i], f[i-1][j-3i]…表示为依次拿了1，2，3…k个i的数字

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];


int main(){

    int n;
    cin >> n;

    for(int i = 1; i <= n; i ++ ) f[i][0] = 1;

    for(int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            f[i][j] = f[i-1][j];
            if (j >= i){
                f[i][j] = (f[i-1][j] + f[i][j - i]) % mod;
            }
        }
    }

    cout << f[n][n] << endl;

    return 0;

}

1.1完全背包优化（一维）

 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N];


int main(){

    int n;
    cin >> n;

    f[0] = 1;

    for(int i = 1; i <= n; i ++ ){
        for (int j = i; j <= n; j ++ ){

            f[j] = (f[j] + f[j - i]) % mod;   // f[i][j] = f[i-1][j] + f[i][j - i] 
                                              // 由于f[i-1][j]表示一个i数字都没拿，不用担心01背包的同一层多拿i的问题。
        }
    }

    cout << f[n] << endl;

    return 0;

}

2. 总和是i, 数字个数有j个的所有方案

状态转移方程：f[i][j] = f[i-1][j-1] + f[i-j][j]

• 其中以最小数字至少有一个1 和 最小数字没有1来划分
• f[i-1][j-1]去掉一个1，那么总和减1，数字的个数减1。表示最小数字至少有一个1。
• f[i-j][j] 所有数字减1，总和减1，数字个数不变，还是正整数，合法。表示最小数字没有1。

 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];


int main(){

    int n;
    cin >> n;
    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ ){
        for (int j = 1; j <= i; j ++ ){
            f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;
        }
    }

    int res;

    for (int i = 0; i < n; i ++ ) res = (res + f[n][i+1]) % mod;

    cout << res << endl;

    return 0;
}

题目描述

如果一个正整数无法被 [2,a] 范围内的任何整数整除，则称其为不合群数。

请你计算并输出 [2,b] 范围内的最大不合群数。

样例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        for (int i = b; i > a; i --) {

            /* 合群标记默认 false */
            boolean hequnFlag = false;

            // 
            for (int j = 2; j <= a && j * j <= i ; j++) {
                if(i % j  == 0){
                    hequnFlag = true;
                    break;
                }
            }
            if( !hequnFlag ){
                // 不合群
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

//3706
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int a = 2, b = 3, c;
    if(n == 1) cout << 2;
    else if(n == 2) cout << 3;
    else{
        for(int i = 3;i <= n;i++){
            c = a + b;
            a = b;
            b = c;
        }
        cout << b;
    }
    return 0;
}

思路：

• 正整数x无法被 [2,a]范围内的任何整数整除
  → x不属于[2, a]

• [2,b]范围内的最大不合群数
  → x属于(a, b]

  → 素数是不合群数

  → 非素数只要无法被[2,a]范围内的数整除也是不合群数

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    int a, b; cin >> a >> b;
    int Max = -1;

    for (int i = b; i > a; i--) 
    {
        bool yes = true;
        for (int j = 2; j <= a && j * j <= i; j++)
            if (i%j == 0) {
                yes = false;
                break;
            }
        if (yes) {
            cout << i << endl;
            return 0;
        }
    } 
    cout << -1 << endl;

    return 0;
}

题目描述

众所周知，对一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$，可以用下述方式求实数解：

• 计算 $\Delta = b ^ 2 - 4ac$，则:
  1. 若 $\Delta < 0$，则该一元二次方程无实数解；
  2. 否则 $\Delta \geq 0$，此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$；
     • 其中，$\sqrt \Delta$ 表示 $\Delta$ 的算数平方根，即使得 $s^2 = \Delta$ 的唯一非负实数 $s$。
     • 特别的，当 $\Delta = 0$ 时，这两个实数解相等；当 $\Delta > 0$ 时，这两个实数解互异。

例如：

• $x ^ 2 + x + 1 = 0$ 无实数解，因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$；
• $x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x_{1, 2} = 1$；
• $x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x_1 = 1, x_2 = 2$；

在题面描述中 $a$ 和 $b$ 的最大公因数使用 $\gcd(a, b)$ 表示。

例如 $12$ 和 $18$ 的最大公因数是 $6$，即 $\gcd(12, 18) = 6$。

现在给定一个一元二次方程的系数 $a, b, c$，其中 $a, b, c$ 均为整数且 $a \neq 0$。

你需要判断一元二次方程 $a x ^ 2 + bx + c = 0$ 是否有实数解，并按要求的格式输出。

在本题中输出有理数 $v$ 时须遵循以下规则：

• 由有理数的定义，存在唯一的两个整数 $p$ 和 $q$，满足 $q > 0$，$\gcd(p, q) = 1$ 且 $v = \frac pq$。
• 若 $q = 1$，则输出 {p}，否则输出 {p}/{q}，其中 {n} 代表整数 $n$ 的值；
• 例如：
  • 当 $v = -0.5$ 时，$p$ 和 $q$ 的值分别为 $-1$ 和 $2$，则应输出 -1/2；
  • 当 $v = 0$ 时，$p$ 和 $q$ 的值分别为 $0$ 和 $1$，则应输出 0。

对于方程的求解，分两种情况讨论：

1. 若 $\Delta = b ^ 2 - 4ac < 0$，则表明方程无实数解，此时你应当输出 NO；
2. 否则 $\Delta \geq 0$，此时方程有两解（可能相等），记其中较大者为 $x$，则：
   1. 若 $x$ 为有理数，则按有理数的格式输出 $x$。
   2. 否则根据上文公式，$x$ 可以被唯一表示为 $x = q_1 + q_2 \sqrt r$ 的形式，其中：
      • $q_1, q_2$ 为有理数，且 $q_2 > 0$；
      • $r$ 为正整数且 $r > 1$，且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$（即 $r$ 不应是 $d ^ 2$ 的倍数）；

此时：

1. 若 $q_1 \neq 0$，则按有理数的格式输出 $q_1$，并再输出一个加号 +；
2. 否则跳过这一步输出；

随后：

1. 若 $q_2 = 1$，则输出 sqrt({r})；
2. 否则若 $q_2$ 为整数，则输出 {q2}*sqrt({r})；
3. 否则若 $q_3 = \frac{1}{q_2}$ 为整数，则输出 sqrt({r})/{q3}；
4. 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$，此时输出 {c}*sqrt({r})/{d}；

上述表示中 {n} 代表整数 $n$ 的值，详见样例。

如果方程有实数解，则按要求的格式输出两个实数解中的较大者。

否则若方程没有实数解，则输出 NO。

输入格式

输入的第一行包含两个正整数 $T, M$，分别表示方程数和系数的绝对值的上界；

接下来 $T$ 行，每行包含三个整数 $a, b, c$。

输出格式

输出 $T$ 行，每行包含一个字符串，表示对应询问的答案，格式如题面所述。

每行输出的字符串中间不应包含任何空格。

数据范围

对于所有测试数据有：$1 \leq T \leq 5000$，$1 \leq M \leq 10 ^ 3$，$|a|,|b|,|c| \leq M$，$a \neq 0$。

其中：

• 特殊性质 $A$：保证 $b = 0$；
• 特殊性质 $B$：保证 $c = 0$；
• 特殊性质 $C$：如果方程有解，那么方程的两个解都是整数。

输入样例：

9 1000
1 -1 0
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1

输出样例：

NO
/
*()
/+()/
+()/
/+*()/

算法1

(大模拟) $O(n^2)$

题目写得很恐怖，其实所代表的意思并不难。
也就是考验你的语文水平和耐心。

不好意思，和同学写规则怪谈写多了，注意事项出现了好多类似“你需要”“不需要”“在遵守”的字眼…

我们梳理一下题意：

给出 一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$，求出在实数范围内较大的 $x$。

然而我们并不需要想如何求解，题目中已经给出了方法。

这里建议先去看懂题目，然后看我们的解题过程，可能会清楚一点。

• 计算 $\Delta = b ^ 2 - 4ac$，则:
  1. 若 $\Delta < 0$，则该一元二次方程无实数解，此时我们输出 NO。记得需要回车。
  2. 否则 $\Delta \geq 0$，此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$；而题目中我们只需要求较大的 $x$ 即可。

从上述的第 $2$ 点开始分类讨论：

（$1$） $\Delta = 0$

我们把 $x$ 的式子抄下来：$x = \frac{-b \pm \sqrt \Delta}{2a}$。

为了方便描述。
我们

将 $-b \pm \sqrt \Delta$ 记为$p$；
将 $2a$ 记为 $q$。

于是 $x = \frac{p}{q}$。

由于此时 $\Delta = 0$
所以 $\sqrt{\Delta} = 0$，所以 $p = -b + \sqrt{\Delta} = -b + 0 = -b$。

接下来我们将分子分母同时除以 $gcd(p,q)$ 使 $x$ 化为最简分式。

同时，我们把分母的负号移到分子上。

由于此时 $\sqrt{\Delta} = 0$ ，所以 $x$ 必为 有理数。
我们直接按分数的输出方法输出 $x$ 即可。

注意: $x$ 可能为整数，此时不要输出 $/q$

（$2$） $\Delta \geq 0$

这种情况会比上面的情况复杂得多，请耐心观看。

首先，我们

将 $-b$ 记为$p$；
将 $2a$ 记为 $q$。
将 $ \sqrt \Delta$ 定义为 $sd$

注意：
1. 此时 $p$ 的定义与上文定义有些许不同，表现为没有 $\pm \sqrt \Delta$。
2. $sd$ 中的 $\sqrt \Delta$ 没有 $\pm$，原因后面讲。
3. $sd$ 变量属性为 $long \ long$，原因后面讲。

此时我们的 $x = \frac{p + sd}{2a}$。

以下分两种情况讨论：

① ${sd}^2 = \Delta$，即 $\Delta$ 为 完全平方数。

由于我们的 $sd$ 为 $long \ long$ 属性，存储时会将 $\sqrt \Delta$ 四舍五入。
那我们就可以根据此种特性判断 $\Delta$ 是否为 完全平方数。（此处解释完成注意事项 $3$）

我们将 $q$ 中的负号移到 分子的$p$ 上。
接着 $p + sd$。

$Q:$ 为什么此处 $p$ 不先加上 $sd$ 再进行$\underline{负号转移}$ （指将分母的负号移到分子上） ？

$A:$ 按问题中所说的方法不能保证 $x$ 为较大解。

为了更加清楚地看到问题，我们设 $p = 4$，$q = -2$，$sd = 3$。

问题中的方法： $x = \frac{4 + 3}{-2} = \frac{-7}{2} = - \frac{7}{2}$
正确的方法： $x = \frac{-4 + 3}{-(-2)} = \frac{-1}{2} = - \frac{1}{2}$

显然正确方法中的 $x$ 更大。

注意事项 $2$ 的意义就是为了不要在此过程中加上绝对值符号，会更加麻烦。

接下来约分后输出

注意： $q = 1$ 时不需要输出 $/q$。

② ${sd}^2 \not= \Delta$，即此时 $\Delta$ 不为 完全平方数。

说一句与分类讨论无关的话：你可能觉得 $sd$ 只是用于判断 $\Delta$ 是否为完全平方数，但事实上不是这样的，我们在后面把 $\sqrt{\Delta}$ 化为最简二次根式时也会用到。所以不要把它写在 $if$ 里面。

由于此时 $\Delta$ 不为完全平方数，所以 $\sqrt{\Delta}$ 为无理数，我们需要将其化为最简二次根式再输出，所以此时我们根据题意改变 $x$ 的表示，分批输出。

$$x = \frac{p}{q} + \frac{ \pm \sqrt{\Delta}}{q}$$

首先我们输出 $x$ 中的 $\frac{p}{q}$。

约为最简分式，将 $q$ 中的负号移到 $p$ 上，输出。（此处说过多次，不再赘述）

注意：

1. 当 $p = 0$ 时 $\frac{p}{q} = 0$ （显而易见），不需要输出
2. 在遵循上述条件 $1$ 的情况下，如果 $q = 1$ ，不需要输出 $/q$

接下来处理后半部分的 $\frac{ \pm \sqrt{\Delta}}{q}$。

我们将 $\sqrt{\Delta}$ 化为最简二次根式（题目中有解释），将其记为 $d1 \sqrt{d2}$。

$Q:$ 如何化简呢？
$A:$ 定义 $d1 = 1$，$d2 = \Delta$。

执行 $for$ 循环，$i$ 从 $sd$ 开始，不断减 $1$，直到 $i = 1$ 为止。（从后往前是为了节约时间）

过程中我们定义 $j = i^2$。
如果 $\Delta$ 能被 $j$ 整除，我们将 $j$ 从根号中开出，将 $d1$ 乘 $i$ ，把 $d2$ 除以 $j$，$break$。

这里怕一些低年级的巨佬没学过二次根式，我们举一个例子：

这里需要知道 $\sqrt{ab} = \sqrt{a} × \sqrt{b}$

此时我们需要化简 $\sqrt{12}$。

根据上述公式我们可以： $\sqrt{12} = \sqrt{4 × 3} = \sqrt{4} × \sqrt{3} = 2 × \sqrt{3} = 2 \sqrt{3}$

然后按照常规方法化简分式，输出。

$Q:$ 为什么 $q$ 赋值时 取了绝对值。（此处见代码 $q = abs(2 * a)$）
$A:$ 与之前 $sd$ 为什么不加 $\pm$ 差不多，是 $x$ 需输出较大值的问题。

我们把后半部分的分式抄下来： $\frac{ \pm \sqrt{\Delta}}{q}$。

• 当 $q$ 为负数时，我们 上方 $ \pm \sqrt{\Delta}$ 取 $- \sqrt{\Delta}$ 时整个分式为正数，显然比负数大
• 当 $q$ 为正数时，我们 上方 $ \pm \sqrt{\Delta}$ 取 $+ \sqrt{\Delta}$ 时整个分式为正数，显然比负数大

这个问题就解决了。

注意：
1. $q = d1$时，$q$ 与 $d1$ 抵消，直接输出 sqrt(d2)即可；
2. $q = 1$时，不需要输出 $/q$；
3. $d1 = 1$时，不需要输出 $d1$。

完结撒花！

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e3 + 10;
long long t,M;
int main(){
    scanf("%lld%lld",&t,&M); // 读入，当然 M 在代码中并没有什么用处（
    while(t --){ // 多测
        long long a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        long long delta = b * b - 4 * a * c; // 计算 delta
        if(delta < 0) printf("NO\n"); // 无解
        else if(delta == 0){ // delta = 0 的情况
            long long p = -b,q = 2 * a;
            long long g = __gcd(abs(p),abs(q));
            p /= g;
            q /= g;
            if(q < 0){
                p = -p;
                q = -q;
            }
            if(q == 1) printf("%lld\n",p);
            else printf("%lld/%lld\n",p,q);
        }
        else{ // delta >= 0 的情况
            long long p = -b,q = 2 * a;
            long long sd = (long long)sqrt(delta);
            if(sd * sd == delta){ // delta 为 完全平方数
                if(q < 0){
                    p = -p;
                    q = -q;
                }
                p += sd;
                long long g = __gcd(abs(p),abs(q));
                p /= g;
                q /= g;
                if(q == 1) printf("%lld\n",p);
                else printf("%lld/%lld\n",p,q);
            }
            else{ // delta 不为 完全平方数
                long long g = __gcd(abs(p),abs(q)); // 前一个分式的处理
                p /= g;
                q /= g;
                if(q < 0){
                    p = -p;
                    q = -q;
                }
                if(p != 0){
                    if(q == 1) printf("%lld+",p);
                    else printf("%lld/%lld+",p,q);
                }
                long long d1 = 1,d2 = delta;
                q = abs(2 * a); // 后一个分式的处理
                for(long long i = sd;i >= 1;i --){
                    long long j = i * i;
                    if(d2 % j == 0){
                        d2 /= j;
                        d1 *= i;
                        break;
                    }
                }
                int gdq = __gcd(abs(d1),abs(q));
                q /= gdq;
                d1 /= gdq;
                if(q < 0){
                    q = -q;
                    d1 = -d1;
                }
                if(q == d1) printf("sqrt(%lld)\n",d2);
                else if(q == 1) printf("%lld*sqrt(%lld)\n",d1,d2);
                else if(d1 == 1) printf("sqrt(%lld)/%lld\n",d2,q);
                else printf("%lld*sqrt(%lld)/%lld\n",d1,d2,q);
            }
        }
    }
    return 0;
}

应该是最为详细的题解了，$AcWing$ 和 $Luogu$ 上都是。

$$（共 355 行）$$

include[HTML_REMOVED]

using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;

}