题目链接： [NOIP2004 普及组] 火星人 - 洛谷 题目描述人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。 火星人用一种非常简单的方式来表示数字

定义排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。 性质稳定性稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。 拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的记录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。 稳

什么是STLSTL称为标准模板库（Standard Template Library），是惠普实验室开发的一系列软件的统称。现主要出现在C++中，STL从广义上分为：容器（Container）、算法（Algorithm）和迭代器（Iterator）。STL几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。 STL六大组件STL提供了六大组件，彼此

问题求出$a^b\mod c$的值，其中a，b，c是整数，且$0<a,c<10^9$，$0<b<10^{18}$ 算法设计暴力算法考虑用循环直接求出$a^b$的值，最后对$c$取模。 123456long long ans=1;for (long long i=1;i<=b;i++){ ans*=a;}ans%=c; 这个代码其实有两个缺陷

介绍扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数$a$，$b$扩展欧几里得算法可以在求得$a$，$b$的最大公约数的同时，找到整数$x$，$y$（其中一个可能是负数），使它们满足$ax+by=gcd(a,b)$。如果a是负数，可以把问题转化成$|a|(-x)+by=gcd(|a|,b)$，然后令$x’=(-x)$。 扩展欧几里得算法可以用来计算模反

介绍欧几里德算法，又叫做辗转相除法，用于计算两个正整数a，b的最大公约数(the greatest common divisor)。 计算公式$$gcd(a,b)=gcd(b,a\mod b)$$ 证明第一步：不妨假设 $c=gcd(a,b)$，则 $a=mc$，$b=nc$，其中 $m，n∈z$ 第二步：取 $r=a-kb=(m-nk)

介绍贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心法是解决问题的一种策略。如果策略正确，那么贪心法往往是易于描述、易于实现的。 经典问题1.背