-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
2357 lines (1982 loc) · 383 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/[email protected]/css/all.min.css" integrity="sha256-2H3fkXt6FEmrReK448mDVGKb3WW2ZZw35gI7vqHOE4Y=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
<script class="next-config" data-name="main" type="application/json">{"hostname":"linkinpony.github.io","root":"/","images":"/images","scheme":"Muse","version":"8.7.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"Searching...","empty":"We didn't find any results for the search: ${query}","hits_time":"${hits} results found in ${time} ms","hits":"${hits} results found"}}</script><script src="/js/config.js"></script>
<meta property="og:type" content="website">
<meta property="og:title" content="I always love dashie">
<meta property="og:url" content="http://linkinpony.github.io/index.html">
<meta property="og:site_name" content="I always love dashie">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="LinkinPony">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="http://linkinpony.github.io/">
<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":true,"isPost":false,"lang":"en","comments":"","permalink":"","path":"index.html","title":""}</script>
<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>I always love dashie</title>
<noscript>
<link rel="stylesheet" href="/css/noscript.css">
</noscript>
<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css">
<!-- hexo injector head_end end --></head>
<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
<div class="headband"></div>
<main class="main">
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="Toggle navigation bar" role="button">
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<i class="logo-line"></i>
<h1 class="site-title">I always love dashie</h1>
<i class="logo-line"></i>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
</div>
</div>
</div>
</div>
<div class="toggle sidebar-toggle" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
<aside class="sidebar">
<div class="sidebar-inner sidebar-overview-active">
<ul class="sidebar-nav">
<li class="sidebar-nav-toc">
Table of Contents
</li>
<li class="sidebar-nav-overview">
Overview
</li>
</ul>
<div class="sidebar-panel-container">
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-overview">
<div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
<p class="site-author-name" itemprop="name">LinkinPony</p>
<div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap site-overview-item animated">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">51</span>
<span class="site-state-item-name">posts</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<a href="/categories/">
<span class="site-state-item-count">11</span>
<span class="site-state-item-name">categories</span></a>
</div>
<div class="site-state-item site-state-tags">
<a href="/tags/">
<span class="site-state-item-count">51</span>
<span class="site-state-item-name">tags</span></a>
</div>
</nav>
</div>
<div class="links-of-author site-overview-item animated">
<span class="links-of-author-item">
<a href="https://github.com/LinkinPony" title="GitHub → https://github.com/LinkinPony" rel="noopener" target="_blank"><i class="github fa-fw"></i>GitHub</a>
</span>
<span class="links-of-author-item">
<a href="https://codeforces.com/profile/LinkinPony" title="CodeForces → https://codeforces.com/profile/LinkinPony" rel="noopener" target="_blank"><i class="code fa-fw"></i>CodeForces</a>
</span>
</div>
<div class="links-of-blogroll site-overview-item animated">
<div class="links-of-blogroll-title"><i class="fa fa-globe fa-fw"></i>
Links
</div>
<ul class="links-of-blogroll-list">
<li class="links-of-blogroll-item">
<a href="https://acker.fun/" title="https://acker.fun/" rel="noopener" target="_blank">Acker</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://kmguan-528.github.io/" title="https://kmguan-528.github.io/" rel="noopener" target="_blank">KMGuan</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</aside>
<div class="sidebar-dimmer"></div>
</header>
<div class="back-to-top" role="button" aria-label="Back to top">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
<noscript>
<div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>
<div class="main-inner index posts-expand">
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://linkinpony.github.io/2023/01/26/MIT-18-06/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="LinkinPony">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="I always love dashie">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2023/01/26/MIT-18-06/" class="post-title-link" itemprop="url">MIT-18.06</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-01-26 13:53:54" itemprop="dateCreated datePublished" datetime="2023-01-26T13:53:54+08:00">2023-01-26</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2023-01-30 09:04:42" itemprop="dateModified" datetime="2023-01-30T09:04:42+08:00">2023-01-30</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E7%AC%94%E8%AE%B0/" itemprop="url" rel="index"><span itemprop="name">笔记</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="lec-4-a-lu">Lec 4 A = LU</h2>
<p><span class="math display">\[
(AB)^{-1} = B^{-1}A^{-1} \\
(A^{T})^{-1} = (A^{-1})^{T}\\
\]</span></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://linkinpony.github.io/2023/01/06/GAMES-202/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="LinkinPony">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="I always love dashie">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2023/01/06/GAMES-202/" class="post-title-link" itemprop="url">GAMES-202</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-01-06 16:38:50" itemprop="dateCreated datePublished" datetime="2023-01-06T16:38:50+08:00">2023-01-06</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2023-01-18 10:46:23" itemprop="dateModified" datetime="2023-01-18T10:46:23+08:00">2023-01-18</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E7%AC%94%E8%AE%B0/" itemprop="url" rel="index"><span itemprop="name">笔记</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="导论">导论</h1>
<h2 id="graphics-hardware-pipeline">Graphics (Hardware) Pipeline</h2>
<figure>
<img src="/.io//image-20230106184441259.png" alt="image-20230106184441259"><figcaption aria-hidden="true">image-20230106184441259</figcaption>
</figure>
<h2 id="opengl">OpenGL</h2>
<p><img src="/.io//image-20230118102300199.png" alt="image-20230118102300199" style="zoom:67%;"></p>
<h3 id="a.-place-objectsmodels">A. Place objects/models</h3>
<p><img src="/.io//image-20230118102922245.png" alt="image-20230118102922245" style="zoom:67%;"></p>
<h3 id="b.-set-up-an-easel">B. Set up an easel</h3>
<p><img src="/.io//image-20230118103116098.png" alt="image-20230118103116098" style="zoom:67%;"></p>
<h3 id="c.-attach-a-canvas-to-the-ease">C. Attach a canvas to the ease</h3>
<p><img src="/.io//image-20230118103323789.png" alt="image-20230118103323789" style="zoom:67%;"></p>
<h3 id="d.-paint-to-the-canvas">D. Paint to the canvas</h3>
<p><img src="/.io//image-20230118104037026.png" alt="image-20230118104037026" style="zoom:67%;"></p>
<p><img src="/.io//image-20230118104438290.png" alt="image-20230118104438290" style="zoom:67%;"></p>
<p><img src="/.io//image-20230118104618634.png" alt="image-20230118104618634" style="zoom:67%;"></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://linkinpony.github.io/2023/01/05/MIT-18-01/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="LinkinPony">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="I always love dashie">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2023/01/05/MIT-18-01/" class="post-title-link" itemprop="url">MIT 18.01 单变量微积分</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-01-05 16:48:45" itemprop="dateCreated datePublished" datetime="2023-01-05T16:48:45+08:00">2023-01-05</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2023-02-01 10:27:59" itemprop="dateModified" datetime="2023-02-01T10:27:59+08:00">2023-02-01</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E7%AC%94%E8%AE%B0/" itemprop="url" rel="index"><span itemprop="name">笔记</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="常用公式">常用公式</h1>
<h2 id="三角函数">三角函数</h2>
<p><span class="math display">\[
\sin^2x + \cos ^ 2 x = 1\\
\]</span></p>
<h2 id="求导">求导</h2>
<h3 id="三角函数求导">三角函数求导</h3>
<p><span class="math display">\[
\sin'x = \cos x\\
\cos'x = - \sin x\\
\tan'x = \frac{1}{\cos^2x} = \sec^2x\\
\arctan' x = \frac{1}{1+x^2}\\
\]</span></p>
<h3 id="指数函数和对数函数">指数函数和对数函数</h3>
<p><span class="math display">\[
\frac{\text d}{\text d x}\ln x = \frac{1}{x}\\
\frac{\text d}{\text d x}e^x = e^x\\
\frac{\text d}{\text dx}a^x = \ln a \cdot a^x\\
\frac{\text d}{\text d x} \ln u = \frac{1}{u}\frac{\text d u}{\text d x}
\]</span></p>
<h1 id="导数derivative">导数（derivative)</h1>
<h2 id="lecture1-导数的几何解释">Lecture1: 导数的几何解释</h2>
<p><img src="/.io//image-20230105165932729.png" alt="image-20230105165932729" style="zoom:67%;"></p>
<p>如图, <span class="math inline">\(P\)</span>点的导数便是过<span class="math inline">\(P\)</span>点的切线(tangent line)的斜率, 记作<span class="math inline">\(f'(P)\)</span>.</p>
<p>什么样子的线是切线? 我们先看由点<span class="math inline">\(PQ\)</span>构成的割线(secant line). 当<span class="math inline">\(PQ\)</span>两点的距离趋于<span class="math inline">\(0\)</span>时, 割线与切线便无限接近.</p>
<p><img src="/.io//image-20230106095142833.png" alt="image-20230106095142833" style="zoom:67%;"></p>
<p>如图. 可得 <span class="math display">\[
f'(x) = \lim_{\Delta x \to 0} \frac{f(x_0 + \Delta x) - f(x_0)}{\Delta x}
\]</span></p>
<h3 id="一些符号">一些符号</h3>
<p><img src="/.io//image-20230106102935887.png" alt="image-20230106102935887" style="zoom:67%;"></p>
<p>导数(牛顿记法): <span class="math inline">\(f'\)</span></p>
<p>导数(莱布尼兹记法): <span class="math inline">\(\frac{\text df}{\text dx},\frac{\text dy}{\text d x},\frac{\text d}{\text dx}f,\frac{\text d}{\text dx}y\)</span></p>
<p>一个有用的公式(推导见手写笔记): <span class="math display">\[
\frac{\text d}{\text d x}x^n = n \cdot x^{n-1}
\]</span></p>
<h2 id="lecture2-极限-连续性和三角函数的极限">Lecture2: 极限, 连续性和三角函数的极限</h2>
<p><img src="/.io//image-20230106105337764.png" alt="image-20230106105337764" style="zoom:67%;"></p>
<p>我们用<span class="math inline">\(\frac{\Delta y}{\Delta x}\)</span>来计量某个函数在一段时间内的平均变化率. 当<span class="math inline">\(\Delta x \to 0\)</span>时, 这便变成了瞬时变化率.</p>
<p><img src="/.io//image-20230106110147320.png" alt="image-20230106110147320" style="zoom:50%;"></p>
<p><img src="/.io//image-20230106110459943.png" alt="image-20230106110459943" style="zoom:67%;"></p>
<p><img src="/.io//image-20230106110512348.png" alt="image-20230106110512348" style="zoom:50%;"></p>
<h3 id="limits-and-continuity">Limits and Continuity</h3>
<p>简单的极限可以直接带入运算:</p>
<p><img src="/.io//image-20230106111047720.png" alt="image-20230106111047720" style="zoom: 67%;"></p>
<p>但是对于 <span class="math display">\[
\lim_{\Delta x \to 0}\frac{\Delta f}{\Delta x}
\]</span> 它不是一个简单极限. 因为我们不能将<span class="math inline">\(\Delta x = 0\)</span>代入运算, 这样永远会得到<span class="math inline">\(\frac{0}{0}\)</span>. <strong>注意</strong>: <span class="math display">\[
\lim_{x \to x_0}
\]</span> 暗示了<span class="math inline">\(x \neq x_0\)</span>.</p>
<h4 id="左右极限left-and-right-limt">左右极限(Left and Right Limt)</h4>
<p>我们用以下两个记号来表示左极限和右极限: <span class="math display">\[
\lim_{x\to x_0^-} (左极限, 此时x < x_0)\\
\lim_{x\to x_0^+} (右极限, 此时x > x_0)\\
\]</span></p>
<h3 id="连续性continuity">连续性(Continuity)</h3>
<p>我们称<span class="math inline">\(f(x)\)</span>在<span class="math inline">\(x_0\)</span>连续, 当且仅当 <span class="math display">\[
\lim_{x \to x_0}f(x) = f(x_0)
\]</span> 这意味着:</p>
<ol type="1">
<li><span class="math inline">\(f(x)\)</span>在点<span class="math inline">\(x_0\)</span>的极限必须存在, 且左右极限相等</li>
<li><span class="math inline">\(f(x_0)\)</span>是有定义的</li>
<li><span class="math inline">\(\lim_{x\to x_0}f(x)\)</span>与<span class="math inline">\(f(x_0)\)</span>相等</li>
</ol>
<p><img src="/.io//image-20230106142515063.png" alt="image-20230106142515063" style="zoom:50%;"></p>
<p>如图, <span class="math inline">\(\lim_{x \to 0^+}f(x) = 1\)</span>, 但是<span class="math inline">\(f(0) = 0\)</span>. 因此该函数在点<span class="math inline">\(0\)</span>不连续.</p>
<p>以下是不连续的几种情况:</p>
<ol type="1">
<li>Removable Discontinuity</li>
</ol>
<p><img src="/.io//image-20230106143147259.png" alt="image-20230106143147259" style="zoom:50%;"></p>
<p>该点的左右极限存在且相等, 但与该点的函数值不等(或该点的函数值未定义)</p>
<ol start="2" type="1">
<li>Jump Discontinuity</li>
</ol>
<p> <img src="/.io//image-20230106142937484.png" alt="image-20230106142937484" style="zoom:50%;"></p>
<p>左右极限均存在, 但不相等.</p>
<ol start="3" type="1">
<li>Infinite Discontinuity</li>
</ol>
<p><img src="/.io//image-20230106143422550.png" alt="image-20230106143422550" style="zoom:50%;"></p>
<p><span class="math inline">\(x = 0\)</span>时, 左极限为负无穷, 右极限为正无穷.</p>
<ol start="4" type="1">
<li>Other (ugly) discontinuities</li>
</ol>
<p><img src="/.io//image-20230106144002234.png" alt="image-20230106144002234" style="zoom:50%;"></p>
<h3 id="导数的图像picturing-the-derivative">导数的图像(Picturing the derivative)</h3>
<p><img src="/.io//image-20230106144101961.png" alt="image-20230106144101961" style="zoom:50%;"></p>
<p>注意导数的图像和原函数的图像没有什么相关性. 而且对一个奇函数求导, 它的导数一定是一个偶函数.</p>
<h3 id="定理-可导必连续theorem-differentiable-implies-continuous">定理: 可导必连续(Theorem: Differentiable Implies Continuous)</h3>
<p><span class="math display">\[
如果f在x_0处可导, 那么f必定在x_0处连续.
\]</span></p>
<p><img src="/.io//image-20230106150417303.png" alt="image-20230106150417303" style="zoom: 80%;"></p>
<h2 id="lecture-3-导数的四则运算及三角函数">Lecture 3: 导数的四则运算及三角函数</h2>
<h3 id="求导公式derivative-formulas">求导公式(Derivative Formulas)</h3>
<p><img src="/.io//image-20230106153822818.png" alt="image-20230106153822818" style="zoom:67%;"></p>
<h3 id="特殊求导公式">特殊求导公式</h3>
<p><span class="math display">\[
\lim_{\theta \to 0}\frac{\sin\theta}{\theta} = 1\\
\lim_{\theta\to0}\frac{1 - cos\theta}{\theta} = 0
\]</span></p>
<p>证明:</p>
<p><img src="/.io//image-20230106160612420.png" alt="image-20230106160612420" style="zoom:67%;"></p>
<p><img src="/.io//image-20230106160652701.png" alt="image-20230106160652701" style="zoom:67%;"></p>
<h4 id="sin-cos">sin, cos</h4>
<p><span class="math display">\[
\frac{\text d}{\text d x}\sin x = \cos x\\
\frac{\text d}{\text d x}\cos x = -\sin x\\
\]</span></p>
<p>推导过程:</p>
<p><img src="/.io//image-20230106154306445.png" alt="image-20230106154306445" style="zoom:67%;"></p>
<h3 id="一般求导公式">一般求导公式</h3>
<ul>
<li><p>加法法则 <span class="math display">\[
(u+v)' = u' + v'
\]</span></p></li>
<li><p>乘积法则</p></li>
</ul>
<p><span class="math display">\[
(uv)' = u'v + uv'
\]</span></p>
<ul>
<li><p>除法法则(quotient rule) <span class="math display">\[
(\frac{u}{v})' = \frac{u'v - uv'}{v^2}(v \neq 0)
\]</span></p></li>
<li><p>证明: 加法法则</p>
<p><img src="/.io//image-20230111103645235.png" alt="image-20230111103645235" style="zoom:67%;"></p></li>
<li><p>证明: 乘法法则</p></li>
</ul>
<p><img src="/.io//image-20230111103618880.png" alt="image-20230111103618880" style="zoom:67%;"></p>
<p><img src="/.io//image-20230111105348577.png" alt="image-20230111105348577" style="zoom:67%;"></p>
<p>几何上的理解: <span class="math inline">\((uv)' \cdot \Delta x = (u + \Delta u)(v + \Delta v) - uv\)</span>, 即图中粉色, 白色, 黄色部分之和. 又因为<span class="math inline">\(\Delta u \cdot \Delta v \approx 0\)</span>, 所以有 <span class="math display">\[
(uv)' \approx \frac{u \Delta v + v \Delta u}{\Delta x} \\
= uv’ +u'v
\]</span></p>
<ul>
<li>证明: 除法法则</li>
</ul>
<p><img src="/.io//image-20230111111834201.png" alt="image-20230111111834201" style="zoom:67%;"></p>
<h2 id="lecture-4链式法则和高阶导数">Lecture 4:链式法则和高阶导数</h2>
<h3 id="链式法则chain-rule">链式法则(Chain Rule)</h3>
<p><span class="math display">\[
\frac{\text{d}y}{\text{d}t} = \frac{\text{d} y}{\text{d}x} \cdot \frac{\text{d}x}{\text{d}t}
\]</span></p>
<p><img src="/.io//image-20230115092644053.png" alt="image-20230115092644053" style="zoom:67%;"></p>
<p><img src="/.io//image-20230115092735531.png" alt="image-20230115092735531" style="zoom: 67%;"></p>
<h3 id="高阶导数higher-derivatives">高阶导数(Higher Derivatives)</h3>
<p><img src="/.io//image-20230115093300221.png" alt="image-20230115093300221" style="zoom:67%;"></p>
<h2 id="lecture-5-隐函数微分及逆函数导数">Lecture 5 隐函数微分及逆函数导数</h2>
<h3 id="隐函数微分implicit-differentiation">隐函数微分(Implicit Differentiation)</h3>
<p>有些函数(例如<span class="math inline">\(x^2 + y^2 = 1\)</span>)不具有明显的<span class="math inline">\(y = f(x)\)</span>形式, 但是能通过变形得到(本例可得<span class="math inline">\(y = \sqrt{1 - x^2}\)</span>). 这样的函数称为隐函数. 对隐函数求导, 可在方程两边同时对<span class="math inline">\(x\)</span>求导, 得到一个包含<span class="math inline">\(\frac{\text{d}y}{\text{d}x}\)</span>的式子, 再求解<span class="math inline">\(\frac{\text{d}y}{\text{d}x}\)</span>即可.</p>
<p><img src="/.io//image-20230115095829432.png" alt="image-20230115095829432" style="zoom:67%;"></p>
<p><img src="/.io//image-20230115095838093.png" alt="image-20230115095838093" style="zoom:67%;"></p>
<p><img src="/.io//image-20230115100903420.png" alt="image-20230115100903420" style="zoom:67%;"></p>
<h3 id="反函数inverse-function">反函数(Inverse Function)</h3>
<p>若<span class="math inline">\(y = f(x),g(x) = y\)</span>, 则<span class="math inline">\(g\)</span>是<span class="math inline">\(f\)</span>的反函数, 记作<span class="math inline">\(f^{-1}\)</span>. 函数和它的反函数关于<span class="math inline">\(y = x\)</span>对称.</p>
<p><img src="/.io//image-20230115104051068.png" alt="image-20230115104051068" style="zoom:67%;"></p>
<p><img src="/.io//image-20230115101543407.png" alt="image-20230115101543407" style="zoom:67%;"></p>
<p><img src="/.io//image-20230115103931577.png" alt="image-20230115103931577" style="zoom:67%;"></p>
<p><img src="/.io//image-20230115103954784.png" alt="image-20230115103954784" style="zoom:50%;"></p>
<p><img src="/.io//image-20230115104005007.png" alt="image-20230115104005007" style="zoom:67%;"></p>
<p><img src="/.io//image-20230115104013455.png" alt="image-20230115104013455" style="zoom:67%;"></p>
<h2 id="lecture-6-指数函数与对数函数对数微分双曲线函数">Lecture 6 指数函数与对数函数，对数微分，双曲线函数</h2>
<h3 id="指数函数对数函数和自然对数">指数函数，对数函数和自然对数</h3>
<p>见课程pdf和手写笔记</p>
<p>### 对数微分(Logarithmic Differentiation)</p>
<p><img src="/.io//image-20230118095423689.png" alt="image-20230118095423689" style="zoom:67%;"></p>
<p><img src="/.io//image-20230118095433488.png" alt="image-20230118095433488" style="zoom:67%;"></p>
<p><img src="/.io//image-20230118101022744.png" alt="image-20230118101022744" style="zoom:67%;"></p>
<p><img src="/.io//image-20230118101033927.png" alt="image-20230118101033927" style="zoom:67%;"></p>
<figure>
<img src="/.io//image-20230118101203685.png" alt="image-20230118101203685"><figcaption aria-hidden="true">image-20230118101203685</figcaption>
</figure>
<h2 id="lecture-7-连续性和第一次考试复习">Lecture 7 连续性和第一次考试复习</h2>
<h3 id="导数伪装的极限">导数伪装的极限</h3>
<p>(普林斯顿微积分读本修订版，人民邮电出版社，ISBN: 978-7-115-43559-0, P101)</p>
<h2 id="leture-9-线性和二阶近似">Leture 9 线性和二阶近似</h2>
<h3 id="线性近似linear-approximation">线性近似(Linear Approximation)</h3>
<p><span class="math display">\[
f(x) \approx f(x_0) + f'(x_0)(x - x_0)
\]</span> <img src="/.io//image-20230130153834142.png" alt="image-20230130153834142" style="zoom:67%;"></p>
<p><img src="/.io//image-20230130154812720.png" alt="image-20230130154812720" style="zoom: 67%;"></p>
<p>注意上表近似符号左边和右边的函数. 如果<span class="math inline">\(f(x_0) + f'(x)(x - x_0)\)</span>比<span class="math inline">\(f(x)\)</span>更容易计算, 便可以用线性近似来加速计算.</p>
<p><img src="/.io//image-20230130162129715.png" alt="image-20230130162129715" style="zoom:67%;"></p>
<p><img src="/.io//image-20230130162139973.png" alt="image-20230130162139973" style="zoom:67%;"></p>
<h3 id="二阶近似quadratic-approximations">二阶近似(Quadratic Approximations)</h3>
<p>一阶(线性)近似可能精度不够, 这时便需要二阶或更高阶的近似. <span class="math display">\[
f(x) \approx f(x_0) + f'(x_0)(x - x_0) + \frac{f''(x_0)}{2}(x-x_0)^2
\]</span></p>
<p>关于为什么二阶导的系数是<span class="math inline">\(\frac{1}{2}\)</span>:</p>
<figure>
<img src="/.io//image-20230201094512497.png" alt="image-20230201094512497"><figcaption aria-hidden="true">image-20230201094512497</figcaption>
</figure>
<p>可以看出, 二阶近似的效果更好:</p>
<p><img src="/.io//image-20230130163838707.png" alt="image-20230130163838707" style="zoom:67%;"></p>
<p>基础的结论:</p>
<p><img src="/.io//image-20230201094623798.png" alt="image-20230201094623798" style="zoom:67%;"></p>
<p><img src="/.io//image-20230201100855010.png" alt="image-20230201100855010" style="zoom:67%;"></p>
<h2 id="lecture-10-曲线构图">Lecture 10: 曲线构图</h2>
<p>Lecture 10: Curve Sketching</p>
<p>利用<span class="math inline">\(f'\)</span>和<span class="math inline">\(f''\)</span>的符号来画出<span class="math inline">\(f\)</span>的近似图像</p>
<ul>
<li><span class="math inline">\(f' > 0\)</span>, <span class="math inline">\(f\)</span>递增. 反之亦然</li>
<li><span class="math inline">\(f'' > 0\)</span>, <span class="math inline">\(f'\)</span>递增, 反之亦然</li>
</ul>
<p>画图的一般步骤:</p>
<p><img src="/.io//image-20230201101459064.png" alt="image-20230201101459064" style="zoom:67%;"></p>
<p>当<span class="math inline">\(f'(x_0) = 0\)</span>时, 点<span class="math inline">\(x_0\)</span>称为驻点(临界点, critical points).</p>
<p>当<span class="math inline">\(f''(x_0) = 0\)</span>时, 点<span class="math inline">\(x_0\)</span>称为拐点(inflection point).</p>
<p><img src="/.io//image-20230201101611151.png" alt="image-20230201101611151" style="zoom:67%;"></p>
<p><img src="/.io//image-20230201101621823.png" alt="image-20230201101621823" style="zoom:67%;"></p>
<figure>
<img src="/.io//image-20230201101928665.png" alt="image-20230201101928665"><figcaption aria-hidden="true">image-20230201101928665</figcaption>
</figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://linkinpony.github.io/2022/08/23/template-math/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="LinkinPony">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="I always love dashie">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2022/08/23/template-math/" class="post-title-link" itemprop="url">[模板]数学</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2022-08-23 09:44:17" itemprop="dateCreated datePublished" datetime="2022-08-23T09:44:17+08:00">2022-08-23</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2022-09-10 19:56:39" itemprop="dateModified" datetime="2022-09-10T19:56:39+08:00">2022-09-10</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E6%A8%A1%E6%9D%BF/" itemprop="url" rel="index"><span itemprop="name">模板</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>[TOC]</p>
<hr />
<p><strong>答案不取模，亲人两行泪</strong></p>
<p>212370440130137957</p>
<p>(↑这是一个很大的质数)</p>
<p>19260817</p>
<p>(↑这是一颗很大的子弹)</p>
<p><strong>判断同余时用</strong><span class="math inline">\((a - b) \mod m== 0\)</span></p>
<p>cout不使用科学计数法输出，设置精度: <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">cout.<span class="built_in">setf</span>(ios::fixed,ios::floatfield);</span><br><span class="line">cout.<span class="built_in">precision</span>(<span class="number">2</span>); </span><br></pre></td></tr></table></figure></p>
<table style="width:6%;">
<colgroup>
<col style="width: 5%" />
</colgroup>
<tbody>
<tr class="odd">
<td># 杂项</td>
</tr>
<tr class="even">
<td>## 神秘结论</td>
</tr>
<tr class="odd">
<td><span class="math display">\[
\sum_{i = 1}^n (d(i))^2 \ll n \log^3 n (d为因子个数)
\]</span></td>
</tr>
<tr class="even">
<td>## 大整数</td>
</tr>
<tr class="odd">
<td>(我也不知道从哪copy)的</td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">bign</span>{</span></span><br><span class="line"> <span class="keyword">int</span> d[maxn], len;</span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">clean</span><span class="params">()</span> </span>{ <span class="keyword">while</span>(len > <span class="number">1</span> && !d[len<span class="number">-1</span>]) len--; }</span><br><span class="line"> </span><br><span class="line"> <span class="built_in">bign</span>() { <span class="built_in">memset</span>(d, <span class="number">0</span>, <span class="built_in"><span class="keyword">sizeof</span></span>(d)); len = <span class="number">1</span>; }</span><br><span class="line"> <span class="built_in">bign</span>(<span class="keyword">int</span> num) { *<span class="keyword">this</span> = num; } </span><br><span class="line"> <span class="built_in">bign</span>(<span class="keyword">char</span>* num) { *<span class="keyword">this</span> = num; }</span><br><span class="line"> bign <span class="keyword">operator</span> = (<span class="keyword">const</span> <span class="keyword">char</span>* num){</span><br><span class="line"> <span class="built_in">memset</span>(d, <span class="number">0</span>, <span class="built_in"><span class="keyword">sizeof</span></span>(d)); len = <span class="built_in">strlen</span>(num);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i < len; i++) d[i] = num[len<span class="number">-1</span>-i] - <span class="string">'0'</span>;</span><br><span class="line"> <span class="built_in">clean</span>();</span><br><span class="line"> <span class="keyword">return</span> *<span class="keyword">this</span>;</span><br><span class="line"> }</span><br><span class="line"> bign <span class="keyword">operator</span> = (<span class="keyword">int</span> num){</span><br><span class="line"> <span class="keyword">char</span> s[<span class="number">20</span>]; <span class="built_in">sprintf</span>(s, <span class="string">"%d"</span>, num);</span><br><span class="line"> *<span class="keyword">this</span> = s;</span><br><span class="line"> <span class="keyword">return</span> *<span class="keyword">this</span>;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> bign <span class="keyword">operator</span> + (<span class="keyword">const</span> bign& b){</span><br><span class="line"> bign c = *<span class="keyword">this</span>; <span class="keyword">int</span> i;</span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i < b.len; i++){</span><br><span class="line"> c.d[i] += b.d[i];</span><br><span class="line"> <span class="keyword">if</span> (c.d[i] > <span class="number">9</span>) c.d[i]%=<span class="number">10</span>, c.d[i+<span class="number">1</span>]++;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span> (c.d[i] > <span class="number">9</span>) c.d[i++]%=<span class="number">10</span>, c.d[i]++;</span><br><span class="line"> c.len = <span class="built_in">max</span>(len, b.len);</span><br><span class="line"> <span class="keyword">if</span> (c.d[i] && c.len <= i) c.len = i+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">return</span> c;</span><br><span class="line"> }</span><br><span class="line"> bign <span class="keyword">operator</span> - (<span class="keyword">const</span> bign& b){</span><br><span class="line"> bign c = *<span class="keyword">this</span>; <span class="keyword">int</span> i;</span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i < b.len; i++){</span><br><span class="line"> c.d[i] -= b.d[i];</span><br><span class="line"> <span class="keyword">if</span> (c.d[i] < <span class="number">0</span>) c.d[i]+=<span class="number">10</span>, c.d[i+<span class="number">1</span>]--;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span> (c.d[i] < <span class="number">0</span>) c.d[i++]+=<span class="number">10</span>, c.d[i]--;</span><br><span class="line"> c.<span class="built_in">clean</span>();</span><br><span class="line"> <span class="keyword">return</span> c;</span><br><span class="line"> }</span><br><span class="line"> bign <span class="keyword">operator</span> * (<span class="keyword">const</span> bign& b)<span class="keyword">const</span>{</span><br><span class="line"> <span class="keyword">int</span> i, j; bign c; c.len = len + b.len; </span><br><span class="line"> <span class="keyword">for</span>(j = <span class="number">0</span>; j < b.len; j++) <span class="keyword">for</span>(i = <span class="number">0</span>; i < len; i++) </span><br><span class="line"> c.d[i+j] += d[i] * b.d[j];</span><br><span class="line"> <span class="keyword">for</span>(i = <span class="number">0</span>; i < c.len<span class="number">-1</span>; i++)</span><br><span class="line"> c.d[i+<span class="number">1</span>] += c.d[i]/<span class="number">10</span>, c.d[i] %= <span class="number">10</span>;</span><br><span class="line"> c.<span class="built_in">clean</span>();</span><br><span class="line"> <span class="keyword">return</span> c;</span><br><span class="line"> }</span><br><span class="line"> bign <span class="keyword">operator</span> / (<span class="keyword">const</span> bign& b){</span><br><span class="line"> <span class="keyword">int</span> i, j;</span><br><span class="line"> bign c = *<span class="keyword">this</span>, a = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = len - <span class="number">1</span>; i >= <span class="number">0</span>; i--)</span><br><span class="line"> {</span><br><span class="line"> a = a*<span class="number">10</span> + d[i];</span><br><span class="line"> <span class="keyword">for</span> (j = <span class="number">0</span>; j < <span class="number">10</span>; j++) <span class="keyword">if</span> (a < b*(j+<span class="number">1</span>)) <span class="keyword">break</span>;</span><br><span class="line"> c.d[i] = j;</span><br><span class="line"> a = a - b*j;</span><br><span class="line"> }</span><br><span class="line"> c.<span class="built_in">clean</span>();</span><br><span class="line"> <span class="keyword">return</span> c;</span><br><span class="line"> }</span><br><span class="line"> bign <span class="keyword">operator</span> % (<span class="keyword">const</span> bign& b){</span><br><span class="line"> <span class="keyword">int</span> i, j;</span><br><span class="line"> bign a = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = len - <span class="number">1</span>; i >= <span class="number">0</span>; i--)</span><br><span class="line"> {</span><br><span class="line"> a = a*<span class="number">10</span> + d[i];</span><br><span class="line"> <span class="keyword">for</span> (j = <span class="number">0</span>; j < <span class="number">10</span>; j++) <span class="keyword">if</span> (a < b*(j+<span class="number">1</span>)) <span class="keyword">break</span>;</span><br><span class="line"> a = a - b*j;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> a;</span><br><span class="line"> }</span><br><span class="line"> bign <span class="keyword">operator</span> += (<span class="keyword">const</span> bign& b){</span><br><span class="line"> *<span class="keyword">this</span> = *<span class="keyword">this</span> + b;</span><br><span class="line"> <span class="keyword">return</span> *<span class="keyword">this</span>;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span> <(<span class="keyword">const</span> bign& b) <span class="keyword">const</span>{</span><br><span class="line"> <span class="keyword">if</span>(len != b.len) <span class="keyword">return</span> len < b.len;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = len<span class="number">-1</span>; i >= <span class="number">0</span>; i--)</span><br><span class="line"> <span class="keyword">if</span>(d[i] != b.d[i]) <span class="keyword">return</span> d[i] < b.d[i];</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span> >(<span class="keyword">const</span> bign& b) <span class="keyword">const</span>{<span class="keyword">return</span> b < *<span class="keyword">this</span>;}</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span><=(<span class="keyword">const</span> bign& b) <span class="keyword">const</span>{<span class="keyword">return</span> !(b < *<span class="keyword">this</span>);}</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span>>=(<span class="keyword">const</span> bign& b) <span class="keyword">const</span>{<span class="keyword">return</span> !(*<span class="keyword">this</span> < b);}</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span>!=(<span class="keyword">const</span> bign& b) <span class="keyword">const</span>{<span class="keyword">return</span> b < *<span class="keyword">this</span> || *<span class="keyword">this</span> < b;}</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span>==(<span class="keyword">const</span> bign& b) <span class="keyword">const</span>{<span class="keyword">return</span> !(b < *<span class="keyword">this</span>) && !(b > *<span class="keyword">this</span>);}</span><br><span class="line"> </span><br><span class="line"> <span class="function">string <span class="title">str</span><span class="params">()</span> <span class="keyword">const</span></span>{</span><br><span class="line"> <span class="keyword">char</span> s[maxn]={};</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i < len; i++) s[len<span class="number">-1</span>-i] = d[i]+<span class="string">'0'</span>;</span><br><span class="line"> <span class="keyword">return</span> s;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"> </span><br><span class="line">istream& <span class="keyword">operator</span> >> (istream& in, bign& x)</span><br><span class="line">{</span><br><span class="line"> string s;</span><br><span class="line"> in >> s;</span><br><span class="line"> x = s.<span class="built_in">c_str</span>();</span><br><span class="line"> <span class="keyword">return</span> in;</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line">ostream& <span class="keyword">operator</span> << (ostream& out, <span class="keyword">const</span> bign& x)</span><br><span class="line">{</span><br><span class="line"> out << x.<span class="built_in">str</span>();</span><br><span class="line"> <span class="keyword">return</span> out;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>使用例:</td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">bign <span class="title">GCD</span><span class="params">(bign a,bign b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="comment">// cout<<"@@@ "<<a<<endl<<"### "<<b<<endl;;</span></span><br><span class="line"> bign k=<span class="number">0</span>,c;</span><br><span class="line"> <span class="keyword">while</span>(b>k)</span><br><span class="line"> {</span><br><span class="line"> c=a%b;</span><br><span class="line"> a=b;</span><br><span class="line"> b=c;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> a;</span><br><span class="line">}</span><br><span class="line"><span class="keyword">int</span> T;</span><br><span class="line"><span class="keyword">int</span> vis[<span class="number">110</span>];</span><br><span class="line">vector <bign> prime;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">GetPrime</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">long</span> <span class="keyword">long</span> i=<span class="number">2</span>;;i+=<span class="number">1</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> flag=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">long</span> <span class="keyword">long</span> j=<span class="number">2</span>;j<i;j+=<span class="number">1</span>)</span><br><span class="line"> <span class="keyword">if</span>(i%j==<span class="number">0</span>) flag=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">if</span>(flag)</span><br><span class="line"> {</span><br><span class="line"> bign k=i;</span><br><span class="line"> prime.<span class="built_in">push_back</span>(k);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span>((<span class="keyword">int</span>)prime.<span class="built_in">size</span>()><span class="number">100</span>) <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> cin>>T;</span><br><span class="line"> <span class="built_in">GetPrime</span>();</span><br><span class="line"> <span class="keyword">while</span>(T--)</span><br><span class="line"> {</span><br><span class="line"> bign n;</span><br><span class="line"> cin>>n;</span><br><span class="line"> bign a=<span class="number">1</span>,b=<span class="number">1</span>,k=<span class="number">1</span>,sum=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">int</span> pos=<span class="number">-1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<<span class="number">100</span>;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(sum*prime[i]<=n) sum=sum*prime[i],pos=i;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<=pos;i++)</span><br><span class="line"> {</span><br><span class="line"> </span><br><span class="line"> b=b*prime[i];</span><br><span class="line"> a=a*(prime[i]+k);</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// cout<<"@@@ "<<s<<endl;</span></span><br><span class="line"> </span><br><span class="line"> }</span><br><span class="line"> bign s=<span class="built_in">GCD</span>(a,b);</span><br><span class="line"> b=b/s,a=a/s;</span><br><span class="line"> cout<<b<<<span class="string">"/"</span><<a<<endl;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> </span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## 随机数发生器</td>
</tr>
<tr class="even">
<td>注意不要用Windows下的<span class="math inline">\(rand()\)</span></td>
</tr>
<tr class="odd">
<td><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">mt19937 Rand(seed);</span><br><span class="line">mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());//cf最好用这个防止被hack</span><br><span class="line">Rand();//返回一个随机数</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="even">
<td>### 均匀分布</td>
</tr>
<tr class="odd">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 包含random头文件</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><random></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="comment">//定义均匀分布对象，均匀分布区间（a,b)为(-10，10)</span></span><br><span class="line"> std::uniform_int_distribution<<span class="keyword">int</span>> uid{ <span class="number">-10</span>,<span class="number">10</span> };</span><br><span class="line"> <span class="comment">//均匀分布区间(a,b)</span></span><br><span class="line"> std::cout << uid.<span class="built_in">a</span>() <<<span class="string">" "</span><< uid.<span class="built_in">b</span>() << std::endl;</span><br><span class="line"> <span class="comment">//定义随机数种子</span></span><br><span class="line"> std::random_device rd;</span><br><span class="line"> <span class="comment">//定义默认随机数生成器</span></span><br><span class="line"> std::default_random_engine dre{ <span class="built_in">rd</span>() };</span><br><span class="line"> std::cout << <span class="string">"五个随机数如下"</span> << std::endl;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < <span class="number">5</span>; ++i)</span><br><span class="line"> std::cout << <span class="built_in">uid</span>(dre) << std::endl;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="even">
<td>## 计时</td>
</tr>
<tr class="odd">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">clock_t</span> start = <span class="built_in">clock</span>();</span><br><span class="line"><span class="comment">// do something...</span></span><br><span class="line"><span class="keyword">clock_t</span> end = <span class="built_in">clock</span>();</span><br><span class="line">cout << <span class="string">"花费了"</span> << (<span class="keyword">double</span>)(end - start) / CLOCKS_PER_SEC << <span class="string">"秒"</span> << endl;</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="even">
<td># 数论</td>
</tr>
<tr class="odd">
<td>## 同余式</td>
</tr>
<tr class="even">
<td>同余属于等价关系, 满足自反、对称、传递三大关系 <span class="math display">\[
\begin{align}
a \equiv a \pmod m\\
a \equiv b \pmod m \iff b \equiv a \pmod m\\
a \equiv b \pmod m \and b \equiv c \pmod m \Rightarrow a \equiv c \pmod m
\end{align}
\]</span> 加、减、乘与一般运算一致. 若<span class="math inline">\(a \equiv b \pmod m\)</span>且<span class="math inline">\(c \equiv d \pmod m\)</span>, 则有 <span class="math display">\[
a+c \equiv b+d \pmod m\\
a-c \equiv b-d \pmod m\\
a*c \equiv b*d \pmod m
\]</span> <strong>除法比较特殊</strong>. 若<span class="math inline">\(ac \equiv bc \pmod m\)</span>, 则 <span class="math display">\[
a \equiv b \pmod{\frac{m}{\gcd(c,m)}}
\]</span></td>
</tr>
<tr class="odd">
<td>其它性质:</td>
</tr>
<tr class="even">
<td><span class="math display">\[
\begin{align}
ax \equiv 0 \pmod p \iff x \equiv 0 \pmod{\frac{p}{\gcd(p,a)}}
\end{align}\\
x \% b == 0 \and \frac{x}{b} \equiv 0 \pmod p \iff x \equiv 0 \pmod{bm}\\
a \equiv b \pmod m \iff a^n \equiv b^n \pmod m\\
a \equiv b \pmod m \and n|m \Rightarrow a \equiv b \pmod n
\]</span></td>
</tr>
<tr class="odd">
<td>## 快速幂</td>
</tr>
<tr class="even">
<td>计算<span class="math inline">\(x^d \mod p\)</span></td>
</tr>
<tr class="odd">
<td>注意<span class="math inline">\(a^b % p = ((a % p)^b) % p\)</span></td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ll <span class="title">Pow</span><span class="params">(ll x,ll d)</span></span>{</span><br><span class="line"> ll tans = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span>(d == <span class="number">0</span>)<span class="keyword">return</span> <span class="number">1</span>%p;</span><br><span class="line"> x %= p;</span><br><span class="line"> ll a = <span class="built_in">Pow</span>(x,d/<span class="number">2</span>);</span><br><span class="line"> tans = a*a%p;</span><br><span class="line"> <span class="keyword">if</span>(d%<span class="number">2</span>)tans = tans*x%p; </span><br><span class="line"> <span class="keyword">return</span> tans%p;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function">LL <span class="title">gcd</span><span class="params">(LL a,LL b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">while</span>(b)</span><br><span class="line"> {</span><br><span class="line"> LL tmp=b;</span><br><span class="line"> b=a%b;</span><br><span class="line"> a=tmp;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> a;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## 一次不定方程</td>
</tr>
<tr class="even">
<td><span class="math inline">\(\sum_{i = 1}^n a_i \cdot x_i = c\)</span>有整数解当且仅当<span class="math inline">\(\gcd(a_1,a_2,...,a_n) | c\)</span></td>
</tr>
<tr class="odd">
<td>## GCD & exGCD</td>
</tr>
<tr class="even">
<td>x,y,d为全局变量.求x和y使得 <span class="math inline">\(ax + by = d\)</span> 且 <span class="math inline">\(|x| + |y|\)</span>最小.</td>
</tr>
<tr class="odd">
<td>其中 <span class="math inline">\(d = gcd(a,b)\)</span></td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ll <span class="title">gcd</span><span class="params">(ll a,ll b)</span></span>{</span><br><span class="line"> <span class="keyword">return</span> b?<span class="built_in">gcd</span>(b,a%b):a;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">gcd</span><span class="params">(ll a,ll b,ll & d,ll & x,ll & y)</span></span>{</span><br><span class="line"> <span class="comment">//notice d = gcd(a,b)</span></span><br><span class="line"> <span class="keyword">if</span>(!b)d = a,x = <span class="number">1</span>,y = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="built_in">gcd</span>(b,a%b,d,y,x);</span><br><span class="line"> y -= x*(a/b);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## 逆元</td>
</tr>
<tr class="even">
<td>返回模p下a的逆.不存在则返回-1.</td>
</tr>
<tr class="odd">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ll <span class="title">inv</span><span class="params">(ll a,ll p)</span></span>{</span><br><span class="line"> ll d,x,y;</span><br><span class="line"> <span class="built_in">gcd</span>(a,p,d,x,y);</span><br><span class="line"> <span class="keyword">return</span> d == <span class="number">1</span>?(x+p)%p:<span class="number">-1</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure> ### 线性筛逆元:</td>
</tr>
<tr class="even">
<td>返回模p下1...n的逆.保存在invs里</td>
</tr>
<tr class="odd">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">get_inv</span><span class="params">()</span></span>{</span><br><span class="line"> inv[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i < maxn;i++){</span><br><span class="line"> inv[i] = (ll)(p - p/i)*inv[p%i]%p;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="even">
<td>## a,b不互质时</td>
</tr>
<tr class="odd">
<td><span class="math display">\[
\frac{a}{b} \mod m = \frac{a \mod (mb)}{b}
\]</span></td>
</tr>
<tr class="even">
<td>证: <span class="math display">\[
\begin{align}
&\frac{a}{b} = km + x (x < m)\\
\Rightarrow \space &a =kbm + bx\\
\Rightarrow \space &a \mod (bm) = bx\\
\Rightarrow \space &\frac{a \mod (bm)}{b} = x\\
\Rightarrow \space &\frac{a \mod (bm)}{b} = \frac{a}{b} \mod m
\end{align}
\]</span></td>
</tr>
<tr class="odd">
<td>## 中国剩余定理(CRT)</td>
</tr>
<tr class="even">
<td>求同余方程组 <span class="math display">\[
\begin{cases} x &\equiv a_1 \pmod {m_1} \\ x &\equiv a_2 \pmod {m_2} \\ &\vdots \\ x &\equiv a_k \pmod {m_k} \\ \end{cases}
\]</span> 在<span class="math inline">\([0,\prod_{i = 1}^nm_i])\)</span>中的解. 要求任意<span class="math inline">\(m_i\)</span>两两互质</td>
</tr>
<tr class="odd">
<td>输入: <code>int n</code> 方程组个数, <code>ll a[] ll m[]</code>,方程组的参数和模数</td>
</tr>
<tr class="even">
<td>复杂度:<span class="math inline">\(O(nlogM)\)</span>, 其中<span class="math inline">\(M\)</span>与<span class="math inline">\(m_i\)</span>同阶</td>
</tr>
<tr class="odd">
<td>输出: 方程组在<span class="math inline">\([0,\prod_{i = 1}^nm_i])\)</span>中的解.</td>
</tr>
<tr class="even">
<td>前置: 逆元</td>
</tr>
<tr class="odd">
<td>调用 <code>CRT(n,a,m)</code></td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ll <span class="title">CRT</span><span class="params">(<span class="keyword">int</span> n,ll * a,ll * m)</span></span>{</span><br><span class="line"> ll M = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>;i <= n;i++)M *= m[i];</span><br><span class="line"> ll ans = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>;i <= n;i++){</span><br><span class="line"> ll mt = M/m[i];</span><br><span class="line"> ll ret = <span class="built_in">inv</span>(mt,m[i]);</span><br><span class="line"> ans = (ans + a[i]*mt%M*ret%M)%M;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> (ans + M)%M;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## Eratosthenes筛</td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">prime</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i <= n;i++){</span><br><span class="line"> <span class="keyword">if</span>(!n_prime[i]){</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j = i*<span class="number">2</span>;j <= n;j += i)n_prime[j] = <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> n_prime[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## 线性筛</td>
</tr>
<tr class="even">
<td><strong>筛素因子时记得直接去掉最后一个素因子, 否则复杂度不对</strong></td>
</tr>
<tr class="odd">
<td>### 线性筛素数</td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">bool</span> not_p[maxn];</span><br><span class="line">vector<<span class="keyword">int</span>>prime;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">euler_sieve</span><span class="params">(<span class="keyword">int</span> n)</span></span>{</span><br><span class="line"> not_p[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i < n;i++){</span><br><span class="line"> <span class="keyword">if</span>(!not_p[i]){</span><br><span class="line"> prime.<span class="built_in">push_back</span>(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> p:prime){</span><br><span class="line"> <span class="keyword">if</span>((ll)p*i >= n)<span class="keyword">break</span>;</span><br><span class="line"> not_p[p*i] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span>(i%p == <span class="number">0</span>)<span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>### 线性筛<span class="math inline">\(\varphi\)</span></td>
</tr>
<tr class="even">
<td><span class="math inline">\(\varphi(n)\)</span>: 小于等于<span class="math inline">\(n\)</span>的正整数中与<span class="math inline">\(n\)</span>互质的数个数</td>
</tr>
<tr class="odd">
<td><span class="math inline">\(\varphi\)</span>的一些性质(以下<span class="math inline">\(p\)</span>代表素数) <span class="math display">\[
\varphi(p) = p-1\\
如果i \% p == 0, \varphi(i*p) = \varphi(i)*p\\
否则\varphi(i*p) = \varphi(i)*(p-1)
\]</span></td>
</tr>
<tr class="even">
<td>phi[n]为<span class="math inline">\(\varphi(n)\)</span>,prime里存的素数</td>
</tr>
<tr class="odd">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> phi[maxn];</span><br><span class="line"><span class="keyword">bool</span> not_p[maxn];</span><br><span class="line">vector<<span class="keyword">int</span>>prime;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">eular_sieve</span><span class="params">(<span class="keyword">int</span> n)</span></span>{</span><br><span class="line"> not_p[<span class="number">1</span>] = phi[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i < n;i++){</span><br><span class="line"> <span class="keyword">if</span>(!not_p[i]){</span><br><span class="line"> phi[i] = i<span class="number">-1</span>;</span><br><span class="line"> prime.<span class="built_in">push_back</span>(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> p:prime){</span><br><span class="line"> <span class="keyword">if</span>((ll)p*i >= n)<span class="keyword">break</span>;</span><br><span class="line"> not_p[p*i] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span>(i%p)phi[i*p] = phi[i]*(p<span class="number">-1</span>);</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> phi[i*p] = phi[i]*p;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="even">
<td>### 线性筛<span class="math inline">\(\mu\)</span></td>
</tr>
<tr class="odd">
<td><span class="math display">\[
\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases}
\]</span></td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> phi[maxn],mu[maxn];</span><br><span class="line"><span class="keyword">bool</span> not_p[maxn];</span><br><span class="line">vector<<span class="keyword">int</span>>prime;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">sieve_mu</span><span class="params">()</span></span>{</span><br><span class="line"> not_p[<span class="number">1</span>] = mu[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i < maxn;i++){</span><br><span class="line"> <span class="keyword">if</span>(!not_p[i]){</span><br><span class="line"> mu[i] = <span class="number">-1</span>;</span><br><span class="line"> prime.<span class="built_in">push_back</span>(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> p:prime){</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">ll</span>(p)*i >= maxn)<span class="keyword">break</span>;</span><br><span class="line"> not_p[p*i] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span>(i%p)mu[i*p] = -mu[i];</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> mu[i*p] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## 杜教筛</td>
</tr>
<tr class="even">
<td>详细请见杜教筛笔记.</td>
</tr>
<tr class="odd">
<td>杜教筛快速筛<span class="math inline">\(\varphi\)</span>和<span class="math inline">\(\mu\)</span>的前缀和.<span class="math inline">\(maxn = n^{\frac{2}{3}}\)</span>时复杂度为<span class="math inline">\(O(n^{\frac{2}{3}})\)</span></td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> maxn = <span class="number">1664510</span>;</span><br><span class="line"><span class="keyword">bool</span> not_p[maxn];</span><br><span class="line">vector<<span class="keyword">int</span>>prime;</span><br><span class="line">ll mu[maxn],phi[maxn];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">sieve</span><span class="params">()</span></span>{</span><br><span class="line"> phi[<span class="number">1</span>] = mu[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i < maxn;i++){</span><br><span class="line"> <span class="keyword">if</span>(!not_p[i]){</span><br><span class="line"> mu[i] = <span class="number">-1</span>;</span><br><span class="line"> phi[i] = i<span class="number">-1</span>;</span><br><span class="line"> prime.<span class="built_in">push_back</span>(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> p:prime){</span><br><span class="line"> <span class="keyword">if</span>(<span class="number">1LL</span>*p*i >= maxn)<span class="keyword">break</span>;</span><br><span class="line"> not_p[i*p] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span>(i%p){</span><br><span class="line"> phi[i*p] = phi[i]*(p<span class="number">-1</span>);</span><br><span class="line"> mu[i*p] = -mu[i];</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> phi[i*p] = phi[i]*p;</span><br><span class="line"> mu[i*p] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>;i < maxn;i++)mu[i] += mu[i<span class="number">-1</span>],phi[i] += phi[i<span class="number">-1</span>];</span><br><span class="line">}</span><br><span class="line">map<<span class="keyword">int</span>,ll>Mu,Phi;</span><br><span class="line"><span class="function">ll <span class="title">du_mu</span><span class="params">(<span class="keyword">int</span> x)</span></span>{</span><br><span class="line"> <span class="keyword">if</span>(x < maxn)<span class="keyword">return</span> mu[x];</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(Mu[x])<span class="keyword">return</span> Mu[x];</span><br><span class="line"> ll tans = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> l = <span class="number">2</span>,r = <span class="number">0</span>;l <= x;l = r+<span class="number">1</span>){</span><br><span class="line"> r = x/(x/l);</span><br><span class="line"> tans -= <span class="number">1LL</span>*(r - l + <span class="number">1</span>)*<span class="built_in">du_mu</span>(x/l);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> Mu[x] = tans;</span><br><span class="line">}</span><br><span class="line"><span class="function">ll <span class="title">du_phi</span><span class="params">(<span class="keyword">int</span> x)</span></span>{</span><br><span class="line"> <span class="keyword">if</span>(x < maxn)<span class="keyword">return</span> phi[x];</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(Phi[x])<span class="keyword">return</span> Phi[x];</span><br><span class="line"> ll tans = <span class="number">1LL</span>*x*(x+<span class="number">1</span>)/<span class="number">2</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> l = <span class="number">2</span>,r = <span class="number">0</span>;l <= x;l = r+<span class="number">1</span>){</span><br><span class="line"> r = x/(x/l);</span><br><span class="line"> tans -= <span class="number">1LL</span>*(r-l+<span class="number">1</span>)*<span class="built_in">du_phi</span>(x/l);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> Phi[x] = tans;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## 欧拉函数<span class="math inline">\(φ(x)\)</span></td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ll <span class="title">cal_phi</span><span class="params">(ll x)</span></span>{</span><br><span class="line"> <span class="keyword">int</span> m = (ll)<span class="built_in">sqrt</span>(x+<span class="number">0.5</span>);</span><br><span class="line"> ll tans = x;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i <= m;i++)<span class="keyword">if</span>(!(x%i)){</span><br><span class="line"> tans = tans/i*(i<span class="number">-1</span>);</span><br><span class="line"> <span class="keyword">while</span>(!(x%i))x /= i;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span>(x > <span class="number">1</span>)tans = tans / x * (x<span class="number">-1</span>);</span><br><span class="line"> <span class="keyword">return</span> tans;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>### 线性筛<span class="math inline">\(φ(x)\)</span></td>
</tr>
<tr class="even">
<td><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">sieve_phi</span><span class="params">(<span class="keyword">int</span> n)</span></span>{</span><br><span class="line"> phi[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>;i <= n;i++)<span class="keyword">if</span>(!phi[i])</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j = i;j <= n;j += i){</span><br><span class="line"> <span class="keyword">if</span>(!phi[j])phi[j] = j;</span><br><span class="line"> phi[j] = phi[j]/i * (i<span class="number">-1</span>);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></td>
</tr>
<tr class="odd">
<td>## 有理数取模</td>
</tr>
<tr class="even">
<td>求<span class="math inline">\(a/b\)</span> % <span class="math inline">\(p\)</span> （p为质数)</td>
</tr>
<tr class="odd">
<td>由费马小定理<span class="math inline">\(b^{p-1} ≡ 1 \pmod p\)</span> 可得 <span class="math inline">\(b^{p-2} ≡ b^{-1} \pmod p\)</span></td>
</tr>
<tr class="even">
<td>故只需求<span class="math inline">\(a*b^{p-2} \bmod p\)</span></td>
</tr>
<tr class="odd">
<td>a,b过大则先膜一下</td>
</tr>
<tr class="even">
<td>## 欧拉定理</td>
</tr>
<tr class="odd">
<td>若<span class="math inline">\(a,p\)</span>互质,则有</td>
</tr>
<tr class="even">
<td><span class="math inline">\(a^{φ(p)} ≡ 1 \pmod p\)</span></td>
</tr>
<tr class="odd">