Skip to content

Commit 781c3ee

Browse files
github-actions[bot]github-actions[bot]
committed
1 parent acaeb5b commit 781c3ee

File tree

175 files changed

+930
-610
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

175 files changed

+930
-610
lines changed

‎1388/404.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,15 +17,15 @@
1717
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="/feed_rss_updated.xml">
1818

1919
<link rel="icon" href="/favicon.ico">
20-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
20+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2121

2222

2323

2424
<title>Algorithms for Competitive Programming</title>
2525

2626

2727

28-
<link rel="stylesheet" href="/assets/stylesheets/main.4af4bdda.min.css">
28+
<link rel="stylesheet" href="/assets/stylesheets/main.2afb09e1.min.css">
2929

3030

3131
<link rel="stylesheet" href="/assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/all-submasks.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Enumerating submasks of a bitmask - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/balanced-ternary.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Balanced Ternary - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/big-integer.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Arbitrary-Precision Arithmetic - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/binary-exp.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Binary Exponentiation - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/bit-manipulation.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Bit manipulation - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/chinese-remainder-theorem.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Chinese Remainder Theorem - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/continued-fractions.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Continued fractions - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/discrete-log.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Discrete Log - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/discrete-root.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Discrete Root - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/divisors.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Number of divisors / sum of divisors - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/euclid-algorithm.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Euclidean algorithm for computing the greatest common divisor - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/extended-euclid-algorithm.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Extended Euclidean Algorithm - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/factorial-divisors.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Finding Power of Factorial Divisor - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/factorial-modulo.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Factorial modulo p - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/factoring-exp.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Factoring Exponentiation - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/factorization.html

Lines changed: 17 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Integer factorization - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">
@@ -6635,6 +6635,12 @@
66356635

66366636

66376637

6638+
6639+
6640+
6641+
6642+
6643+
66386644

66396645

66406646

@@ -6727,6 +6733,10 @@
67276733

67286734

67296735

6736+
6737+
6738+
6739+
67306740

67316741

67326742

@@ -6739,7 +6749,7 @@
67396749
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
67406750

67416751
Last update:
6742-
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="April 16, 2024 21:08:03">April 16, 2024</span>&emsp;
6752+
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="April 15, 2025 02:32:08">April 15, 2025</span>&emsp;
67436753

67446754
<!-- Tags -->
67456755

@@ -6942,7 +6952,9 @@ <h2 id="pollards-rho-algorithm">Pollard's rho algorithm<a class="headerlink" hre
69426952
If <span class="arithmatex">$p$</span> is smaller than <span class="arithmatex">$\sqrt{n}$</span>, the repetition will likely start in <span class="arithmatex">$O(\sqrt[4]{n})$</span>.</p>
69436953
<p>Here is a visualization of such a sequence <span class="arithmatex">$\{x_i \bmod p\}$</span> with <span class="arithmatex">$n = 2206637$</span>, <span class="arithmatex">$p = 317$</span>, <span class="arithmatex">$x_0 = 2$</span> and <span class="arithmatex">$f(x) = x^2 + 1$</span>.
69446954
From the form of the sequence you can see very clearly why the algorithm is called Pollard's <span class="arithmatex">$\rho$</span> algorithm.</p>
6945-
<center>![Pollard's rho visualization](pollard_rho.png)</center>
6955+
<div style="text-align: center;">
6956+
<img src="pollard_rho.png" alt="Pollard's rho visualization">
6957+
</div>
69466958

69476959
<p>Yet, there is still an open question.
69486960
How can we exploit the properties of the sequence <span class="arithmatex">$\{x_i \bmod p\}$</span> to our advantage without even knowing the number <span class="arithmatex">$p$</span> itself?</p>
@@ -7095,7 +7107,7 @@ <h2 id="practice-problems">Practice Problems<a class="headerlink" href="#practic
70957107

70967108
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
70977109
<span class="contributors-text">Contributors:</span>
7098-
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (85.05%)</li><li><a href="https://github.com/chloeimb" title="chloeimb" data-bi-name="contributorprofile" target="_blank">chloeimb</a> (9.81%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (3.51%)</li><li><a href="https://github.com/0xGodspeed" title="0xGodspeed" data-bi-name="contributorprofile" target="_blank">0xGodspeed</a> (0.7%)</li><li><a href="https://github.com/pokorj54" title="pokorj54" data-bi-name="contributorprofile" target="_blank">pokorj54</a> (0.47%)</li><li><a href="https://github.com/jxu" title="jxu" data-bi-name="contributorprofile" target="_blank">jxu</a> (0.23%)</li><li><a href="https://github.com/kyomukyomupurin" title="kyomukyomupurin" data-bi-name="contributorprofile" target="_blank">kyomukyomupurin</a> (0.23%)</li></ul>
7110+
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (84.42%)</li><li><a href="https://github.com/chloeimb" title="chloeimb" data-bi-name="contributorprofile" target="_blank">chloeimb</a> (9.77%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (3.49%)</li><li><a href="https://github.com/mhayter" title="mhayter" data-bi-name="contributorprofile" target="_blank">mhayter</a> (0.7%)</li><li><a href="https://github.com/0xGodspeed" title="0xGodspeed" data-bi-name="contributorprofile" target="_blank">0xGodspeed</a> (0.7%)</li><li><a href="https://github.com/pokorj54" title="pokorj54" data-bi-name="contributorprofile" target="_blank">pokorj54</a> (0.47%)</li><li><a href="https://github.com/jxu" title="jxu" data-bi-name="contributorprofile" target="_blank">jxu</a> (0.23%)</li><li><a href="https://github.com/kyomukyomupurin" title="kyomukyomupurin" data-bi-name="contributorprofile" target="_blank">kyomukyomupurin</a> (0.23%)</li></ul>
70997111
</ul>
71007112

71017113
</article>

‎1388/algebra/fft.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Fast Fourier transform - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

‎1388/algebra/fibonacci-numbers.html

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,15 @@
2323
<link rel="alternate" type="application/rss+xml" title="RSS feed of updated content" href="../feed_rss_updated.xml">
2424

2525
<link rel="icon" href="../favicon.ico">
26-
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.11">
26+
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.6.12">
2727

2828

2929

3030
<title>Fibonacci Numbers - Algorithms for Competitive Programming</title>
3131

3232

3333

34-
<link rel="stylesheet" href="../assets/stylesheets/main.4af4bdda.min.css">
34+
<link rel="stylesheet" href="../assets/stylesheets/main.2afb09e1.min.css">
3535

3636

3737
<link rel="stylesheet" href="../assets/stylesheets/palette.06af60db.min.css">

0 commit comments

Comments
 (0)