Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
adamant-pwn merged 17 commits intocp-algorithms:mainfrommdeapedro:patch-1
Oct 15, 2024

Conversation

mdeapedro
Copy link
Contributor

Add 'GCD of multiple numbers' section.

Add 'GCD of multiple numbers' section.
@mdeapedromdeapedro changed the titleUpdate euclid-algorithm.mdAdd 'GCD of multiple numbers' section in euclid-algorithm.mdOct 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
ContributorAuthor

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

@jxu
Copy link
Contributor

jxu commentedOct 13, 2024
edited
Loading

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
ContributorAuthor

Indeed.

@adamant-pwn
Copy link
Member

adamant-pwn commentedOct 13, 2024
edited
Loading

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.

reverofevil and mdeapedro reacted with heart emoji

@adamant-pwnadamant-pwn deleted the branchcp-algorithms:mainOctober 14, 2024 18:53
@adamant-pwnadamant-pwn changed the base branch frommaster tomainOctober 14, 2024 19:17
@github-actionsGitHub Actions
Copy link
Contributor

github-actionsbot commentedOct 14, 2024
edited
Loading

Preview the changes for PR#1355 (for commit38982cb) athttps://gh.cp-algorithms.com/1355/.

@github-actionsGitHub Actions
Copy link
Contributor

Preview the changes for PR#1355 (for commitcbb7b39) athttps://gh.cp-algorithms.com/1355/.

github-actionsbot pushed a commit that referenced this pull requestOct 15, 2024
github-actionsbot added a commit that referenced this pull requestOct 15, 2024
github-actionsbot added a commit that referenced this pull requestOct 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-pwnadamant-pwn merged commitaeeac92 intocp-algorithms:mainOct 15, 2024
2 checks passed
github-actionsbot added a commit that referenced this pull requestOct 15, 2024
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

4 participants
@mdeapedro@reverofevil@jxu@adamant-pwn

[8]ページ先頭

©2009-2025 Movatter.jp