飞机降落

N 架飞机准备降落到某个只有一条跑道的机场。其中第 i架飞机在 Ti时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di个单位时间，即它最早可以于 Ti​ 时刻开始降落，最晚可以于 Ti+Di时刻开始降落。降落过程需要 Li个单位时间。一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。请你判断 NN 架飞机是否可以全部安全降落。

输入格式 ： 输入包含多组数据。

第一行包含一个整数 T，代表测试数据的组数。

对于每组数据，第一行包含一个整数 N。

以下 N行，每行包含三个整数：Ti，Di​ 和 Li​。

输出格式

对于每组数据，输出 YES或者 NO，代表是否可以全部安全降落。

回溯法或者穷举法都一样。

平方拆分

将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方法？注意交换顺序视为同一种方法，例如 13^2+25^2+35^2=2019 与 13^2+35^2+25^2=2019 视为同一种方法。

直接回溯法

123

小蓝发现了一个有趣的数列，这个数列的前几项如下： 1,1,2,1,2,3,1,2,3,4,⋯ 小蓝发现，这个数列前 1 项是整数 1，接下来 2 项是整数 1 至 2，接下来 3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依次类推。 小蓝想知道，这个数列中，连续一段的和是多少。

输入描述 :输入的第一行包含一个整数 T，表示询问的个数。 接下来 T 行，每行包含一组询问，其中第 i 行包含两个整数 li和 ri，表示询问数列中第 i个数到第 ri 个数的和。

输出描述 : 输出 T 行，每行包含一个整数表示对应询问的答案。

•对于所有评测用例，1≤T≤100000,1≤li≤ri≤10^12。

方法思路

反倍数

给定三个整数 a,b,c，如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。请问在 1 至 n 中有多少个反倍数。

•输入描述

•输入的第一行包含一个整数 n。

•第二行包含三个整数 a,b,c，相邻两个数之间用一个空格分隔。其中，1≤n≤1000000，1≤a≤n，1≤b≤n，1≤c≤n。

•输出描述 

输出一行包含一个整数，表示答案。

直接暴力破解。

𝐴=2^3^4^…^2022^2023   𝑚𝑜𝑑 2023

用中国剩余定理去求解比较容易：2023=7*17*17 

容易得出，

A= 1 mod  7

A=2 mod 289

A=869 mod 2023

双子星的讯息

在夜空下，双子星闪烁，据说它们藏着宇宙的秘密。天文学家小蓝守着古朴的望远镜，翻开一本泛黄的星图。图上标注了两串数字：20255202 和 10244201。旁边的笔记写道：若有一正整数 n，使 n+20255202 与 n+10244201 均为完全平方数，便能解锁双子星的讯息。小蓝点亮油灯，决心追寻答案。

a^2-b^2=10011001=7*11*13*73*137， 且a>b,  有几组解？

a-b任取0个，1个，2个，3个因子，各有1，5，7，1个解。

四平方和定理，又称为拉格朗日定理

每个正整数都可以表示为至多 4 个正整数的平方和。 如果把 0 包括进去，就正好可以表示为 4 个数的平方和。 比如： 5=0^2+0^2+1^2+2^2； 7=1^2+1^2+1^2+2^2；

对于一个给定的正整数，可能存在多种平方和的表示法。 要求你对 4 个数排序：0≤a≤b≤c≤d 并对所有的可能表示法按 a,b,c,d为联合主键升序排列，最后输出第一个表示法。

输入描述

程序输入为一个正整数 N(N<5×10^6))。

输出描述

要求输出 4 个非负整数，按从小到大排序，中间用空格隔开。

代码解释

1. 预处理：初始化 first_c 和 first_d 数组为 -1，表示尚未找到解。然后遍历所有可能的 c和 d，计算 s=c^2+d^2，如果 s 在范围内且尚未被记录，则存储当前的 c 和 d。

2. 枚举a和b：遍历 a 和 b，计算剩余值 rest。如果 rest 无法表示为两个平方数之和，则跳过。

3. 检查解：如果预处理中的解满足 c≥b，则输出结果。否则，遍历可能的 c，检查是否存在 d 使得 c^2+d^2=rest 且 d≥c。

4. 终止条件：一旦找到满足条件的解，立即输出并终止程序，确保效率。

这种方法通过预处理和高效枚举，确保了在较大输入范围内快速找到解。

#include <iostream>
#include <cmath>
using namespace std;

const int MAX_N = 5000000;
int first_c[MAX_N + 1];
int first_d[MAX_N + 1];

int main() {
    int N;
    cin >> N;
    
    for (int i = 0; i <= MAX_N; i++) {
        first_c[i] = -1;
    }
    
    int sqrtN = sqrt(N);
    for (int c = 0; c <= sqrtN; c++) {
        for (int d = c; d <= sqrtN; d++) {
            long long s = c * c + d * d;
            if (s > N) break;
            if (first_c[s] == -1) {
                first_c[s] = c;
                first_d[s] = d;
            }
        }
    }
    
    for (int a = 0; a <= sqrtN; a++) {
        for (int b = a; b <= sqrtN; b++) {
            long long a2b2 = a * a + b * b;
            if (a2b2 > N) break;
            int rest = N - a2b2;
            if (rest < 0) break;
            if (first_c[rest] == -1) continue;
            if (first_c[rest] >= b) {
                cout << a << " " << b << " " << first_c[rest] << " " << first_d[rest] << endl;
                return 0;
            } else {
                int start_c = b;
                int end_c = sqrt(rest / 2);
                if (end_c < start_c) continue;
                for (int c = start_c; c <= end_c; c++) {
                    int d2 = rest - c * c;
                    if (d2 < 0) break;
                    int d = sqrt(d2);
                    if (d * d == d2 && d >= c) {
                        cout << a << " " << b << " " << c << " " << d << endl;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入描述

输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1 ∼ AN​ 并不一定是按等差数列中的顺序给出)

其中，2≤N≤10^5，0≤Ai≤10^9。

输出描述

输出一个整数表示答案。

输入输出样例

5 2 6 4 10 20

示例

10

排序后用gcd求出公差 d

奇怪的捐赠

地产大亨 Q 先生临终的遗愿是：拿出 100 万元给 X 社区的居民抽奖，以稍慰藉心中愧疚。麻烦的是，他有个很奇怪的要求：100 万元必须被正好分成若干份（不能剩余）。每份必须是 7的若干次方元。比如：1元, 7元， 49 元，343 元，...相同金额的份数不能超过 5份。在满足上述要求的情况下，分成的份数越多越好！请你帮忙计算一下，最多可以分为多少份？

相同金额的份数不能超过 5份， 就是把100万表示成七进制就是答案， 而且是唯一的答案。

100万转成7进制 1000000=7^7+7^6+3*7^5+3*7^4+3*7^3+7^2+7

所以共有1+1+3+3+3+3+1+1=16

有奖问答

小蓝正在参与一个现场问答的节目。活动中一共有 30道题目, 每题只有答对和答错两种情况, 每答对一题得 10分，答错一题分数归零。

小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 100 分, 所以到达 100 分时小蓝会直接停止答题。请注意小蓝也可能在不到 100 分时停止答题. 已知小蓝最终实际获得了 70 分对应的奖项, 请问小蓝所有可能的答题情况有多少种?

类似于图的深度优先遍历， 用回溯法求解即可。 

费马的秘密遗物

在古老的阿尔法大陆，有一个被称为“费马的遗物”的神秘物品。据传闻，这个遗物是费马大师亲手制作的神秘计算器。阿尔法大陆的居民们相信，它可以预测未来、解决困境、甚至改变命运。但要启动这个神秘的遗物，需要快速求出密码，由于人力运算速度不够快，你希望能够借助计算机来快速完成计算。

现在给定三个正整数 a,b,p，其中 p 是一个质数，目的是求 a^bmod  p的值。成功计算出这个值可能是启动“费马的遗物”的关键。

输入格式

一行三个整数 a,b,p 。其中 1≤a,b≤10^9, 2≤p≤10^7 且 p 是质数。

输出格式

输出一个整数，表示 a^bmod  p的值。

样例输入

3 4 5

样例输出

1

这是著名的模平方指数算法。 

阶乘的和

问题描述

给定 n 个数 Ai，问能满足 m!为∑i=1^n(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1×2×3×⋯×m。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数，分别表示 Ai​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

3
2 2 2

样例输出

3

int main() {
	int n;
	cin >> n;
	vector<long long> A(n);
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	long long min_val = A[0];
	map<long long, int> freq;
	for (long long num : A) {
		freq[num]++;
	}

	long long current = freq[min_val];
	long long i = min_val + 1;
	while (current % i == 0) {
		current /= i;
		if (freq.find(i) != freq.end()) {
			current += freq[i];
		}
		i++;
	}

	cout << i - 1 << endl;
	return 0;
}

避免直接计算m!的和。 

阶乘的位数

9 的阶乘等于：362880362880, 它的二进制表示为：1011000100110000000, 这个数字共有 1919 位。 请你计算，99999999 的阶乘的二进制表示一共有多少位？

一个数n的二进制位数可以通过log2(n) + 1来， 9999！的二进制位数就是log2(9999!)+1。斯特林公式：n! ≈ √(2πn) * (n/e)^n，所以，log2(n!) ≈ log2(√(2πn)) + n * log2(n/e) ，更精确地：log2(n!) = (1/2) * log2(2πn) + n * log2(n) - n * log2(e) + O(1/n)近似等于118444.855， 

共有118445位。 

取模