介绍了不定方程、同余、欧拉函数、逆元、中国剩余定理的相关知识

不定方程

形如 $ax + by = c$,其中 $a$, $b$, $c$ 是已知数的方程被称为二元一次不定方程。它有解当且仅当 $\gcd(a,b)\mid c$

我们可以通过扩展欧几里得算法求不定方程:

void exgcd(int a, int b, int &x, int &y) {
if (a % b == 0) {
x = 0;
y = 1;
} else {
exgcd(b, a % b, y, x);
y -= a / b \* x;
}
}

同余

这是一个同余式:

$$a \equiv b \pmod p $$

同余式两侧可以加减乘但不能直接除

威尔逊定理

正整数 $p$ 是质数的充要条件为 $(p-1)!\equiv-1\pmod p$

欧拉函数

欧拉函数 $\varphi(n)$ 表示小于 $n$ 的数中与 $n$ 互质的数的个数

特别地 $\varphi(1)=1$

欧拉函数有:

  • 积性 如果 $\gcd(a,b)=1$,$\varphi(a \times b)=\varphi(a)\times \varphi(b)$
  • 欧拉反演 ???
  • 对于质数 $p$,$\varphi(p^k)=p^k-p^{k-1}$ (只有 $p$ , $2p$ 至 $p^{k-1}p$ 共 $p^{k-1}$ 个数与 $p^k$ 不互质)

你设 $n$ 的唯一分解式为 $n=p\\_1^{k\\_1} p\\_2^{k\\_2}\ldots p\\_s^{k\\_s}$,则根据积性算出 $\varphi(n)=\Pi\_{i=1}^s \varphi(p\_i^{k\_i})$,而 $\varphi(p\_i^{k\_i})$ 是可根据上面第三条推算出的

逆元

同余式可以加减乘但不能直接除,所以我们希望得到一个数 $x^{-1}$ 使得任何数除 $x$ 等价于乘 $x^{-1}$

$x$ 的逆元表示为 $x^{-1}$。逆元满足

$$x\times x^{-1}\equiv 1 \pmod p$$

  1. $x$ 在模 $p$ 同余下存在逆元当且仅当 $\gcd(x,p)=1$
  2. 在模 $p$ 同余下,$x$ 的逆元若存在则唯一
  3. 一个数的逆元的逆元等于它本身
  4. 在模质数 $p$ 同余下,$[1,p-1]$中所有整数的逆元互不相同

那怎么求呢

费马小定理

在模 $p$ 同余下,$x$ 的逆元为 $x^{p-2}$

线性求

$inv\_i$ 表示 $i$ 的逆元
$$inv\_i=-\lfloor \frac{p}{i} \rfloor \times inv\_{p \mod i} \pmod p$$

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (1ll \* (p - (p / i)) \* inv[p % i]) % p;

用exgcd

由于 $x\times x^{-1}\equiv 1 \pmod p$ 它等价于 $xx^{-1}=kp+1\leftrightarrow xx^{-1}+kp=1$ 其中 $x$、$p$ 是已知量,$x^{-1}$、$k$是未知量,带入exgcd exgcd(x,p,ans,y) 即可

中国剩余定理 CRT

$$\quad \left\{ \begin{matrix} x \equiv a\_1 \pmod {m\_1} \\ x \equiv a\_2 \pmod {m\_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a\_n \pmod {m\_n} \end{matrix} \right.$$

保证 $m$ 中数互质

$t\_i$ 是 $M\_i$ 模下 $m\_i$的逆元;$M=\Pi m\_i$;$M\_i=M \div m\_i$

$$x\equiv \sum a\_i t\_i M\_i \pmod M$$

模板题:P1495 【模板】中国剩余定理(CRT)/ 曹冲养猪。结合exgcd求逆元:

int inv(int a, int d) {
int x, y;
exgcd(a, d, x, y);
return (d + x % d) % d;
}

新疆!

Day 1

去新疆玩喽!七点我就起床了,吃完早饭收拾完行李我们就出发了,12点左右到达机场,托运安检完之后去吃了一个赛百味的大鸡肉三明治当中午饭吃,吃完发现可以登机了就赶紧跑到登机口通过廊桥登上了空客320。起飞后看了一会书就发了飞机餐,飞机餐是肉丸饭、绿豆糕和面包,另外还配上了一份好像有点辣的香菇酱,爸爸说可以塞到面包里吃(黑暗料理!),但他自己拌饭吃了。

降落之后我们来到了乌鲁木齐市,入住了酒店,然后安检后去当地的“大巴扎”(了一大串烤羊肉串,付完35元之后我们说我们不要辣,但师傅仍然抓起了一大把辣椒做出要往上撒的架势。我们见状赶紧大叫“不要辣!不要辣!”,可师傅朝我们一笑,原来他是在逗我们玩!我们恍然大悟,赶紧接过羊肉串大快朵颐起来。“啊!”这刚出锅的羊肉串的铁串十分烫,我差点被烫了一大口,这真是“心急吃不了热豆腐”!还没享用完美味的羊肉串妈妈就发现了下一个美食——烤包子。因为普通的烤包子卖完了我们只好买贵5元的“和田烤包子”,它顾名思义就是被烤过了的包子,里面是羊肉洋葱(本地叫皮牙子)外皮是焦焦的,十分好吃(吗?)。再往前我们看到了我们此程一直在寻找的新疆烤馕!妈妈十分激动,赶紧买了一个15元的高级肉囊。咬完外面厚厚的囊边就来到了中间美味的部分:羊肉的肉香味混合着面粉的清香,让人欲罢不能。最后我们体验了“卡瓦斯”,它是黄色的,尝起来有一股酒味,但其实没有添加任何酒精,是使用新疆的蜂蜜酿成的!十分神奇(假装我喝过酒了!)。最后我们还吃了当地的“老汉瓜”,它拥有着十分坚硬的外皮,但里面软软面面的,也十分的甜,比我们平时吃的哈密瓜甜多了!

回到酒店已经是十点钟了,但是天才开始黑,这是因为新疆在中国的北部,天黑较晚,大约十点才日落,而今天正好是夏至,是一年中白天最长的一天。

2023/6/24 22:02 At 乌鲁木齐火车站

Day 2

今天早上八点吃完早饭就坐车去了火洲吐鲁番,对,就是那个西游记里的火焰山的所在地!我们坐高铁来吐鲁番,可途中高铁突然停住了,为什么呢?旅客们众说纷纭,有的说是要让汽车走,有的说是要会车……到了之后我们发现这次停车是不在计划内的,大屏幕上显示我们延误了11分钟。

不管怎么样我们都到达了吐鲁番,一到我们就感觉热了不少,可是导演说今天“太凉快了”,今天的最高温度“只有”40摄氏度,应该“再高一点让我们体验一下”。

首先我们来到了坎儿井,它是中国古代三大工程之一。它从天山为吐鲁番提供了珍贵的水源,让他们繁衍生息,生活到今天。首先我们体验了坎儿井的水:十分凉爽,果然是从天山上引出来的。然后我们了解了它的结构:首先人们从天山到村庄每隔一段距离挖一个坑(称为“竖井”),越里村庄坑深越浅,然后人们下坑,将坑底挖联通,再把村庄的坑引到村里供人们使用。我们还参观了竖井、竖井下奔流不息的水,导游告诉我们,古人在修坎儿井时要弓着身子,十分不容易,我们体会到了古人们的智慧和勤劳!最后我们还看到了用土砖砌成的葡萄干晾房,是用来晒葡萄干的。

然后用完午饭我们来到了葡萄沟的一户人家中,他热情地招待了我们并为我们介绍了哈萨克族的民族文化,比如绿帽子在他们那一个村只有三个人能戴:村长、队长和负责招待的人,而戴的时候如果帽尖朝前就证明未婚,边朝前就已婚(帽子是正方形的)……然后他为我们介绍带货了当地的葡萄干。其中有一种“suo suo”的小小葡萄干是可以治病的,感冒发烧可以把它熬成水治。

最后我们就来到了火焰山!火焰山由于有矿物所以表面是红色的,而夕阳西下时天空也是红的,所以看起来像是着火了一样。进入景区映入眼帘的是一根大“金箍棒”,它其实是个温度计,上面有指示地面温度,今天虽然只有40度,但地面温度也达到了75度!我们甚至能感觉到热浪涌来,我们赶紧在上面拍了照,打了卡,又买了一张照片就赶紧跑掉了。

晚上回到了乌鲁木齐,去吃“海尔八格”大饭店,可是手抓饭没有了也没有告诉我们,害得我们等了“一会”(几十分钟),换成了炒饭,饭店为了表示歉意给我们送了甜点。回到房间就已经是快十一点了。

2023/6/24 23:20 At 去北屯的卧铺上

Day 3

并不早起去看天山,坐了半个小时的盘山大巴车就到达了山顶,我们看到了小天池,它是漏斗形的,人们至今都没有测量出它的深度。它是青色的,给人一种神幻莫测的感觉。再往上就可以看到天池,它处在群山之间,群山被云雾缭绕着,还有的山上有着常年不化的积雪,甚至有一座山上下起了小雨!我赶紧拍了两张照片,然后……就下雨了,我们赶紧跑回服务中心吃我们的泡面大餐,后来雨就没有停,没带雨衣的我们就只好一直躲在服务中心里。过了几小时,导游决定带我们下山,天山之旅就这样遗憾的结束了。以后如果有机会再来新疆我要再来天山!

下山后就前往火车站,在火车站洗漱完之后我写了一会这个游记就上车了。我们坐的是软卧,从走道里看去,每四个床有独立的包间、门,左右分成上下铺,而硬卧则没有门,一个包间有六个床,左右则是上中下三个床。我们放完行李就应该睡觉了,但我们看了一会儿乌鲁木齐的夜景才睡。这床十分窄,大概只有半米宽,睡着一翻身就掉下去了,所以我没有睡在上铺,让妈妈睡上铺。轰隆轰隆……我们在火车的声音中入睡了(吗?)

PS:关于为什么日期都是 2023/6/24 左右:因为前几天太忙了,没有时间写,只好坐卧铺的时候写

2023/6/25 7:30 At 去北屯的卧铺上

Day 4

轰隆轰隆轰隆轰隆……火车飞快的驶向北屯,我掀开窗帘,太阳才刚刚出来,把周围的天空染成了红色,云朵也被染成了梦幻的粉色,映衬着下面广阔无比的戈壁滩,别有一番滋味。戈壁滩十分荒芜,只有一丝丝绿色,许久才看见一两个蒙古包,一群牛羊。我们趁着没人,赶紧先去洗漱了。过了一会,列车员过来提醒我们马上该下车了。

下了火车就去北屯吃了早饭,坐了两三小时大巴车我们终于来到了喀纳斯,吃完午饭又坐了一小时车终于入住了酒店。这些盘山公路十分晕人,有些晕车的人赶紧去买了晕车药。

喀纳斯十分具有自然风光,还没有进景区就看到了成群结对的牛羊在草原(或者山)上,碧蓝的草原/山上点缀着几朵蓝色的、白色的小花,时不时还会有哈萨克族的“毡房”,它与蒙古包基本相同,唯一的不同就是毡房的门是不会往西开的,而蒙古包则通常向东。景区里还有大片的杉树在山的阴凉处,给人视觉的享受。而我们入住的酒店也十分有特色,是木头盖的,隔音效果不好,但保暖很好,在寒冷的喀纳斯有着很好的效果!而酒店外形是三角形的,可能是因为三角形是最稳定的,但最主要的原因是冬天喀纳斯下雨下雪时,堆积在房子上的雨雪可能有几吨重,三角形会让雨雪不停留在屋顶直接掉下来。

入住之后导游带我们参观喀纳斯湖。途中遇到了一只可爱的小松鼠,赶紧留影!

我们在途中也遇到了许多美景,这里简直就是“随手都能拍出大片”的地方啊!比如湛蓝的天空、留有积雪的山峰配上绿色的草原再加上旁边的牛羊热情出场,为画面增加一点动感。往前就到了游船码头,我们坐上游船,前往喀纳斯湖的第三湾。在那里,我们在绿山和有积雪的山前拍了照,忽然发现水中有一顶帽子在孤独地漂流着,一定是风大,它的主人没有戴紧。船鸣笛之后我们就返程了!我们一回到码头狂风就刮了起来,导游让我们回售票大厅躲一下雨,果然不一会儿暴雨如注,我们都庆幸回来了。

雨停了之后我们就决定回酒店,可是半路太阳出来了,我们认为天下过雨了就不会再下了,于是继续参观。“哇!”随着团友们的一声声感叹,我发现了一道彩虹!赤橙黄绿青蓝紫,真是一道美丽而又标准的彩虹啊!它挂在半山腰上,像一座大桥一样把两座山连在了一起。忽然大家发现山顶上还有一个小彩虹,它的颜色很淡,不注意看根本看不出来。惊叹过后大家赶紧摆出各种造型拍起照来。彩虹只持续了五分多钟就结束了。望向四周,每个山上都笼罩着一层薄雾,像是披了一层纱。

我们沿着喀纳斯湖边走,遇到了很多美景:蓝天、绿树、蓝色(或绿色)的湖水,赶紧拍照!最后“我在喀纳斯很想你”的路牌也吸引大家打卡。

2023/6/25 23:08 At 喀纳斯的酒店

Day 5

早上起床吃完牛肉面就乘车前往山顶的观鱼台,但车只把我们送到了半山腰我们需要爬1068级台阶才能到。刚到时晨雾还未消散开,望向山路远处是一团白雾,观鱼台根本看不到。随着我们沿着台阶向上爬,四周的景物慢慢清楚起来,远处是碧绿的山上长满了杉树,树像是复制的一样,没有空隙地长满了群山;近处则是蓝的、红的、粉的和白的野花遍布草坪,让人眼花缭乱,给人一种在瑞士的感觉。

不一会儿我们就接近了观鱼台,它是一个金色的圆球顶上插上了两个小翅膀,像传说在喀纳斯湖里的水怪一样。旁边,雾气消散了一半,正好留下了蓝色、波光粼粼的湖面、远处的雪山和绿色的山脉在镜头中。咔嚓~一张桌面壁纸就产生了。登上观鱼台就能看到四国风光,这是因为这里地处边境线,距离最近的邻国大约只有10千米。可是说来也奇怪,这里是观鱼的,可是一条鱼我们都没看到,更别提水怪了(拍到了景区奖励100万元!),倒是风景秀丽,适合拍照。

从观鱼台回来就要自己去吃午饭了,但考虑到才吃早饭没多久我们就只点了一杯布丁奶茶。喝完后我们就骑马去喊泉了!我骑的是一匹黑马,由一个在另一个马上的小伙牵着,一起牵着的还有妈妈的大白马。我根据小伙说的,把一只脚踏在马鞍脚踩的地方,再往右一晃,骑在马鞍上,最后握住马鞍上的把手就骑好了!妈妈也准备好了之后我们就出发了!刚开始感觉马走路时一抖一抖的上下摇晃,我们握紧把手,手都不敢松,但后来慢慢适应了,就开始欣赏沿途的风景了:我们从森林中穿过,身旁全是像宝塔一样圆锥形的云杉,时不时还有平原,欢乐的马儿就时而奔腾,时而散步。妈妈的马一定是太兴奋了,不时超到前面去,小伙让妈妈这时拉紧缰绳,马果然是走慢了点。哇,前面有一条小溪!马不慌不忙地踏了进去,激起浪花,妈妈的马一定是渴了,抓住机会就低头喝水,小伙只好让他的领头马走快一点,赶紧离开小溪。

大约骑了一个小时又走了几分钟我们到达了喊泉。这其实就是一个小水塘,神奇之处在于如果有人对着它喊它底部的沙子会像底下有水往上灌一样翻滚,但它始终都是那个水位。据说成吉思汗曾经用过这些水清洗创口,结果不久就好了,因此当地人十分敬仰这些水,水塘上的树枝还绑了彩带。

我们回程时仍然骑马,我们发现马不时会发出奇怪的声音,同时头使劲往下滴,询问发现这是马在打喷嚏,原来不止我们人会打喷嚏呀!

骑完马我们就去参观喀纳斯湖的三道湾。首先我们来到了神仙湾,这里白天看只是一个普通的小湾只不过背景很好看,但其实早上晨雾还没来得及消散的时候过来可以看到薄雾漂浮在湖面上,当第一缕阳光照上去的时候薄雾也被染成了金黄色,当然这些纯属想象我可不会起早来看 有兴趣的你们可以上网搜一搜。然后就到达了月亮湾,这个湾里有两个由水下植物形成的阴影部分,形似两个脚印,很像是有人站在这留下的。最后我们就来到了卧龙湾,同样也是由水下植物组成的阴影部分,形似恐龙睡在湖里(不是神话里的中国龙),因而得名。

结束后我们离开景区,入住酒店,开始享用烤全羊!羊被烤好了之后举行了仪式,由一位老人在羊头上划一个“十”,寓意十全十美,再从脖子划到尾巴,寓意忘了。然后热情的服务员给我们跳了一段双人的舞蹈,还随机邀请妈妈一起跳!结束之后就享用了美味可口的烤全羊,大人们喝了“弄死你们”的乌苏啤酒(logo倒着看是“msnm”)就回去睡觉了。

2023/6/26 21:55 At 喀纳斯外的酒店

Day 6

早上坐了两小时的车之后到达了禾木入住酒店、吃中饭,然后去参观禾木的图瓦人的“博物馆”。在中国的图瓦人大约有三千人,他们有自己的语言但没有自己的文字,我们参观了他们住的木屋,它是用木头穿插而制成的,全屋没有用一根钉子。而木头与木头之间则是苔藓,它让木屋冬暖夏凉:夏天苔藓干了,有缝隙通风很凉快;冬天苔藓则会膨胀,起到保暖的效果。这个“博物馆”是当年俄罗斯人建的,距今已有百年历史,所以这是“百年老屋”。然后我们去听了他们的民族音乐,其中有一种像笛子一样的乐器,是由在特定的季节采摘的一种植物的茎做成的,学习成本也很高,村里只有一位老人会吹出所有音符。还有一个当地的非遗是一个木箱子上有一个小木头,它会随着音乐节奏而跳跃,十分神奇!

然后我们就回到客房,休息之后去烤羊肉串喽!导游给我们买了两条羊腿,又找来煤球生起火来,眼看煤就要烧起来了,几个无聊的小朋友放了几个新的煤球,可是不小心打破了平衡,把导游辛辛苦苦生的的煤球都弄灭了,这下导游又只好再生一次。过了半小时,火生好了,几个爸爸来把羊腿切成小块再按肥瘦分类,就轮到妈妈们穿了!她们把肉按照瘦肉、瘦肉、肥肉、瘦肉、肥肉、瘦肉的顺序穿到签上,这就是“疆”右边的结构:三横表示新疆的三个山;两个田字表示两个盆地。而签的第一个和最后一个肉需要折着穿进去,这样可以起到固定的作用。其实由于妈妈们人数不够,我们小朋友们也充当起妈妈穿羊肉串了。穿到一半就可以烤肉了,在导游一番指导之后小朋友们就烤起肉来:只见他们抓起一把羊肉串摆在烧烤架上撒上一把孜然、一把盐,还时不时翻个面,颇有大师风范!幽默的导游说:“明天我们回家就从烤羊肉串大学毕业了!”他还时不时叫着:“羊肉串羊肉串喽!正宗的新疆羊肉串!”吸引其它团友来吃。他说,以前他带团在路边烤羊肉串还真有路人听了“吆喝声”过来买羊肉串!为什么不去淄博吃?

吃完了羊肉串我们爬楼梯登上了观景台俯瞰整个禾木村。在这里,禾木村大大小小的木屋、从村中流过的河水、茂密的绿树林相映成趣,再配上日落的夕阳、远处的群山和近处的白桦林,就形成了一卷极美的画卷。拍完了照,我们就下观景台,进入了白桦林,这里全是树皮白色的白桦树,这里的白桦树虽不如妈妈说的俄罗斯的那么粗,但细的树干也有一番情趣。风吹过树林,白桦树叶随风飘动,像一个个小铃铛。

我们经过了禾木桥,我发现桥上的“禾木”两个字的桥名就是用切下来的白桦树枝拼成的,真是就地取材啊!然后我们去吃了晚饭,导游推荐羊肉火锅但我们不饿,只吃了一碗炒饭、一盘拌面,拌面是厨师拿着一团面,拉出一条面下一条,所以吃起来十分有嚼劲。

今天晚上在禾木村,光污染很少,所以理论上来说能看到银河,导游建议凌晨两点左右看。

2023/6/28 23:34 At 北屯火车站

Day 7

凌晨一点半爸爸喊我起来看星星,我披上外套,一出房门,抬头发现漫天繁星闪耀(实际上我没看到有星星在闪),我们也不认识多少星星,就认识北斗七星,长长的勺柄、接近正方形的勺子在空中闪耀着,让人一眼就能认出它,而它的勺柄指向北方,有时间验证一下。因为太困了所以赶紧回到床上,好像起的太早了或是天气不好有雾所以没有看到银河。

早上吃了我们人均30元的早餐就去坐公交车玩,因为是循环的坐到底站不用动就可以坐回来,我们坐了一圈欣赏风景之后就回酒店收拾行李。好了之后我们去白桦林玩、拍照片和视频。

然后我们就去吃中饭(早上起晚了),我们的“中饭”有两碗西瓜、两串羊肉串、一个馕,加起来人均13元,非常便宜!吃完之后我们坐了几小时车到达布尔津吃了晚饭,然后去福海玩。这其实就是一个很大的湖,但新疆人没有见过海,觉得这个湖很大就称它为海。我们下了车就被蚊子包围了,这里蚊子很多,但新疆有个地方蚊子平均每立方米有1000只!现在正好是日落,景色很美,远方的群山隐隐约约能看到,伴随着湖边的潮水声,让人感觉到十分宁静。这里还可以捡石头,甚至有概率捡到玉石,但玉石应该已经被前面的游客捡走了,轮不到我们了!

拍完照玩了一会我们就受不了蚊子赶紧上车去火车站。接近凌晨零点上了卧铺返回乌鲁木齐市。

2023/6/29 16:05 At 乌鲁木齐机场

Day 8

卧铺睡得挺香的,到达之后参观新疆自治区博物馆,看到了干尸,然后去大大巴扎旁边的小饭店吃了炸串串,果然不在景区就是便宜,只花了26块钱!然后喝了两杯核桃仁酸奶就去机场坐飞机回南京。

2023/6/29 16:28 At 乌鲁木齐机场

$$End$$


五一去庐山玩咯~

Day 1

由于五一票太难定所以我们的旅行团只尽力给我们订到了每家一个一等座,其他人只能现场补站票。

一大早就被喊醒了~花了一刻钟打打到了去南站的车,七点整到达。为了补偿我们(只有站票)旅行团让我们去贵宾休息室休息,旅行团还十分贴心的为早起没吃早饭的我们每人准备一份包含汉堡、鸡蛋的早餐。在吃完早饭之后就开始检票了,我们通过VIP通道上了车并随后补了大家的站票。我经过艰难的抉择之后在车厢连接处用小马扎坐了半程,又在后半程体验了一把一等座:座位变得更加宽敞,原来一行六个座位改成了四个;还有一排两个的插头;在前面还有专门的脚踏板,舒服多了!

在三个小时后我们到达了庐山站,我们吃了一顿很有特色的饭:许多菜都是辣的,即使不辣也很烫,要等待一会儿。但鸡汤味道还是很不错的,还加入了当地的许多菇,这就是“新鲜的食材,往往只需要简单的烹饪了”。最棒的是招牌的红烧肉,颜色红润,油而不腻,入口即化,饭店一天只做两次。

用餐完毕后我们乘坐大巴来到白鹿洞书院,这里是古代的最高学府,在当时就相当于现在的清华北大。首先我们参观了两棵桂花树,它们可非同一般哦!它们的花都是橙色的,不同于现在的黄色的花。当然,因为“折桂”是及第的意思所以桂花在白鹿洞书院中广泛种植,在桂花盛开的季节,听导游说,在检票口都可以被桂花香醉晕 ^\_^。然后我们又参观了理学家朱熹的画像,是他把白鹿洞书院规模扩大并创建了学田制,即,学生自给自足,不用依靠人民的捐款。然后我又参观了孔子的画像,他是所有学生永远的老师。然后我们又了解了朱熹的白鹿洞教条,我们熟知的“己所不欲勿施于人”就出自这里。我们又前往极星门拍照留念:它是老建筑,而状元桥又在它后面,所以在这里留影并走过状元桥被认为可以考上状元!

结束之后我们启程去“横看成岭侧成峰,远近高低各不同”的庐山。检票之后我们坐上了索道,几分钟后我们到了山顶,别看只有这几分钟的车程,这里气温和山底下要差好几度呢,就如“人间四月芳菲尽,山寺桃花始盛开”一样。到了之后我们入住酒店,享用了同样很辣的晚餐后就去牯岭街逛街,去邮局!听说买东西可以免费盖邮戳就花五块钱买了个白鹿洞书院的信封盖满邮戳:有仙人洞,牯岭街的日期戳,还有文字配图片的庐山会议旧址,三叠泉…非常有纪念意义!

Day 2

今天早上本来想去含鄱口看日出的,但爸爸告诉我们昨天有雾今天早上肯定看不见日出(找理由不想去),可导游却说昨天起雾今天晴天正好适合看日出,真是机不可失,时不再来!

起床后我们去自助餐厅吃早饭,我嗦了江西很有名的粉,它十分丝滑,光溜溜的,再配上青菜和配料,简直就是人间美味!吃完后我们来到了含鄱口,这里就是看日出的地方。我们爬上了最高点,拍了一张全景,这里天格外的蓝,蓝天上懒洋洋的飘着几丝白云,远处还能看见旁边的鄱阳湖,两旁是庐山的最高峰和五老峰:五老峰看起来就像是侧面的躺着的主席,有眼睛、鼻子、嘴巴,还有中山装的领子;而据说天气好时站着最高峰上可以看到武汉的灯火!然后我们去著名的题着“水光山色含鄱口”字的石门下拍照打卡。

看完含鄱口我们就前往三叠泉,在排了大约半个小时队之后我们坐上了网红小火车(虽然我不觉得,不就是一个车厢下一个轨道吗),又下了一会儿山,就到达了最底下。在这里往上看可以看到三叠泉的全貌:在最顶上的一条水流砸在岩石上,分成两条,这两条又砸在岩石上,形成了一整道水帘,汇入底下的龙潭。我们在拍完照之后就返程了,没有去龙潭洗手(万一洗了手被龙发现了怎么办(doge)。

在上山之后排了一会队就坐小火车回去吃饭了。饭真的不怎么样,这是因为本来我们安排出三叠泉吃的,但集合的时间也比较晚了,没有时间出去吃了。

吃完饭了之后我们就排了四十分钟队做大巴车出三叠泉到达美庐。美庐是蒋介石和妻子宋美龄的庐山别墅,他们夏天就从南京来庐山避暑,因此庐山也是他们的副都。当然,毛泽东也住过美庐,他在胜利后在这里住过。美庐中的所有家具都是原样保持的,给我们一种历史的沉淀感。我看到了会客厅、卧室中的真皮沙发和桌子,蒋介石还在这里指挥过战斗呢。院子里有块石头,上面是蒋介石亲笔题写的“美庐”两字,据说毛泽东的工作人员差点把它铲了,被毛泽东制止了,他说:“这就是历史,要尊重历史”。

参观结束之后因为走得太累,我们买了三份泡面晚上在客房吃。

Day 3

早上吃完早饭坐了大巴去花径。看了花径旁的如琴湖,它的名字取自在高空俯瞰它的样子——一把琴,在湖中央还有一座小岛,就像镜面的一颗珍珠。在此之后我们去参观了花径。进了花径是白居易题的一句话,白居易在江西做官时有钱有闲,游遍了江西。再往前一点就是一棵看似普通的树,但如果你轻抚它的书皮,你就会发现它的不同之处:它的树枝会轻轻晃动,就像人怕痒痒一样,它因此得名“痒痒树”,它的学名叫紫薇。随后是一棵大树,它的名字叫做“麦吊云杉”,这是因为它的树叶就像麦穗一样,只不过是倒着的,看上去就是吊着的麦穗,再往前就是一个亭子,它里面放着一个石头,上面写着“花径”两字,古代人曾经猜测是白居易手书,但它的“花”字的写法跟今天一样,唐代还没有这种写法,所以大家懂的,最后就是白居易的草堂,但这个草堂不是真的,真的在庐山的半山腰,这个是复制品。草堂中有白居易的雕塑、简介,还有白居易的书房(也有可能是卧室),还有一个诗词填空小游戏。

看完花径我们就来到了仙人洞,沿着小路走一段就可以到达第一个景观—天桥,这里是一个天然形成的桥,但它是断的,只有两头,没有中间。传说朱元璋打仗时被逼到这里,大叫“天亡我也”,忽然一条金龙从天而降,把断桥补全,帮助他过去,从那以后就没有君主过桥了。再往前走就到了断崖,这里往下看是万丈深渊,也是主席题诗“无限风光在险峰”的地方。在这里向下俯瞰,两座大山林立左右,中间夹着九江市区,再远处就是飘渺的山峰、碧蓝的天空。往前走不远就看见一群人围在护栏边,原来是一只野生猕猴在林中嬉戏,它从石头下爬上来,露出它金色的皮毛,又纵身一跃,跳到一旁的树枝上,一松手,晃进下面的树林里,一溜烟跑没影了,可惜的是它全程都没有给我们一张正脸。猴子跑掉了大家就继续往前走,到达了仙人洞(对,才到),这是天然的山洞,也是道家的寺庙,供着一尊大佛,再往里面是一个泉水,从古至今,无论是丰水期还是枯水期它都滴着水,应该形成了水滴穿石的景观(太暗没看见)。

看完之后我们就沿着出口出去了。出口的门叫做“月亮门”,象征家庭圆满、幸福,门两边的对联则体现了庐山道教、佛教和平相处的特点。再往前是一个朱元璋御造的小亭子,亭子中间是一个石碑,上面书写着一个故事,大概意思是一个疯和尚帮助朱元璋实现统一大业。听导游说朱元璋造完后亭子是四面开的,但有人告诉他北面对着长江,财气会从北门跑走,所以他就赶紧把那个门堵住了,所以现在这里是三面开。

吃过午饭之后我们参观了庐山会议旧址,这里一共举行过三次重要会议,但会场因为维修不能进去,只能在一楼的博物馆里了解会议。

下午两点我们结束了三天的庐山行程,坐缆车下山,乘高铁回家了。


图论的笔记

Kruskal

最大/小生成树算法

一棵 $n$ 个节点的树可以理解为一个 $n$ 个节点; $n-1$条边的连通图(一个节点可以到达任意一个其它节点)

即,断开一条边,树分为两个连通块。则断开 $k$ 条边树被分为 $k+1$ 个连通块。

生成树是什么?

从一张 $n$ 个节点 $m$ 条边的图中选出 $n-1$ 条边,组成一个(连通的)树

最小生成树:边权最小的生成树;最大生成树相反。

反向考虑一棵树的构建过程:

一开始是 $n$ 个独立的点(连通块),然后每增加一条边就减少一个连通块。我们可以使用并查集来实现连通块的维护。

要构建一颗最小生成树,只要按照边权升序排序,依次考虑。

那怎么考虑呢?对于要考虑的两个节点 $u$、$v$,通过并查集查看它们是否在同一连通块中(find(u)==find(v)),如果是则不选(这样会形成环而最终的树中不应该有环);否则可以选。

Kruskal算法的流程:

1.初始化并查集
2.按边权排序,依次扫描每条边:

  • 如果 $u$、$v$ 在同一连通块中,扫描下一条;
  • 否则选择

动态算法演示

Dijkstra

解决单源最短路径(SSSP)的算法

流程:

$ dis(x) $ 表示从起点 $S$ 到 $x$ 的最短距离

  • 初始化 $dis(S)$ 为 $0$,其它为 正无穷
  • 在未被标记的节点中找到 $dis$ 最小的并标记
  • 将上一步找到的最小的设为 $x$,扫描 $s$ 的所有出边 $(x,y,z)$(即从 $x$ 到 $y$ 的距离为 $z$),如果 $dis(y)>dis(x)+z$就更新 $dis(y)$

它只能处理非负边权!

时间复杂度为 $O(n^2)$


并查集是一种动态维护多个不重复集合

在并查集中,每个集合都有自己的代表元素。

一个树 $ fa $ 记录每一个元素的归属关系(存储所属集合代表元素的下标)。

具体:

初始状态:

即,每个元素都是一个单独的集合

int fa[mxn];
for (int i = 0; i < n; i++) fa[i] = i;

常见操作

Get

查询一个元素属于哪一个集合(通常题目中会问两个元素是否属于同一集合)

int find(int x) {
if (fa[x] == x) return x;
return find(fa[x]);
}

(查询某元素所属集合的代表元素)

那么请考虑这样一种情况:

它退化成了一条链!这样时间复杂度就会大大增加!那么假如元素直接指向代表元素,那假如代表元素迁移(见后)了呢?就在find时实时更新呗!

`
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}


仔细观察代码你会发现只添加了 `fa[x]=` 这几个字。这就是路径压缩

(有点像记忆化搜索?

查询两个元素是否属于同一集合的代码也很简单

bool is\_in\_one\_set(int b, int c){
return find(b) == find(c);
}


# Merge

把两个元素 $ a $、$ b $ 所在的集合合并为一个

![](/usr/uploads/63172f524d5b.png)

随意修改 $ a $、$ b $ 中一个的父元素为另一个的父元素

void merge(int a, int b) {
int fa\_ = find(a);
int fb = find(b);
fa[fa\_] = fb;
}