Skip to content

Add 'GCD of multiple numbers' section in euclid-algorithm.md #1355

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 17 commits into from
Oct 15, 2024

Conversation

mdeapedro
Copy link
Contributor

Add 'GCD of multiple numbers' section.

Add 'GCD of multiple numbers' section.
@mdeapedro mdeapedro changed the title Update euclid-algorithm.md Add 'GCD of multiple numbers' section in euclid-algorithm.md Oct 13, 2024
@reverofevil
Copy link

Awaiting for a separate article about a sum of several numbers.

I don't see why this is useful.

@mdeapedro
Copy link
Contributor Author

I think it's useful because it's often requested in contests, and it's not very obvious.

@jxu
Copy link
Contributor

jxu commented Oct 13, 2024

We can simply have a sentence saying gcd is associative, so we can define gcd(a, b, c) as gcd(a, gcd(b, c)) and so forth.
The code is trivial.

@mdeapedro
Copy link
Contributor Author

Indeed.

@adamant-pwn
Copy link
Member

adamant-pwn commented Oct 13, 2024

If we're adding this, I think it's worthwhile to mention that finding $\gcd(a_1,\dots,a_n)$ where $a_i \leq C$ with Euclidean algorithm would take $O(n + \log C)$, rather than $O(n \log C)$, as every non-trivial iteration of the Euclidean algorithm reduces the current GCD candidate by at least a factor of $2$. But this part is better to add at the end of the "time complexity" section.

@adamant-pwn adamant-pwn deleted the branch cp-algorithms:main October 14, 2024 18:53
@adamant-pwn adamant-pwn reopened this Oct 14, 2024
@adamant-pwn adamant-pwn changed the base branch from master to main October 14, 2024 19:17
Copy link
Contributor

github-actions bot commented Oct 14, 2024

Preview the changes for PR #1355 (for commit 38982cb) at https://gh.cp-algorithms.com/1355/.

Copy link
Contributor

Preview the changes for PR #1355 (for commit cbb7b39) at https://gh.cp-algorithms.com/1355/.

github-actions bot pushed a commit that referenced this pull request Oct 15, 2024
github-actions bot added a commit that referenced this pull request Oct 15, 2024
github-actions bot added a commit that referenced this pull request Oct 15, 2024
@adamant-pwn
Copy link
Member

Thanks! And sorry for repeated merges of main into patch-1, I needed to check how pull requests preview work.

@adamant-pwn adamant-pwn merged commit aeeac92 into cp-algorithms:main Oct 15, 2024
2 checks passed
github-actions bot added a commit that referenced this pull request Oct 15, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants