Skip to content
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.

Sign up for GitHub

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

Jump to bottom

Add 经由变换加速的大数乘法和三模数FNTT #4230

Open
Great-designer opened this issue Aug 19, 2022 · 3 comments
Open

Add 经由变换加速的大数乘法和三模数FNTT #4230

Great-designer opened this issue Aug 19, 2022 · 3 comments
Labels
Content Request / 内容请求 New feature or request

Comments

@Great-designer
Copy link
Contributor

Great-designer commented Aug 19, 2022 •
edited

页面英文名

无，直接续在NTT后面

我希望能添加的内容是

传说中的三模数FNTT，最好有代码。
@Great-designer Great-designer added the Content Request / 内容请求 New feature or request label Aug 19, 2022
@Great-designer
Copy link
Contributor Author

发现借助普通的FFT计算大数乘法的部分都没有……

@hly1204
Copy link
Contributor

hly1204 commented Sep 5, 2022

中国剩余定理的 Garner 算法已经给出了做法.

@Great-designer Great-designer changed the title Add 三模数NTT Add 经由变换加速的大数乘法和三模数NTT Sep 5, 2022
@Great-designer
Copy link
Contributor Author

Great-designer commented May 31, 2023 •
edited by unfurl-links bot

提供一个资料
https://www.cnblogs.com/Narh/p/10035325.html

题目：https://www.luogu.org/problemnew/show/P4245 三模数NTT： 大概是用3个模数分别做一遍，用中国剩余定理合并。 前两个合并起来变成一个 long long 的模数，再要和第三个合并的话就爆 long long ，��以可以用一种让两个模数的乘积不出现的方

@Great-designer Great-designer changed the title Add 经由变换加速的大数乘法和三模数NTT Add 经由变换加速的大数乘法和三模数FNTT Jun 6, 2023
@Great-designer Great-designer mentioned this issue Jun 6, 2023
Closed
1 task
@yuhuoji yuhuoji mentioned this issue Sep 12, 2023
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Content Request / 内容请求 New feature or request
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@hly1204 @Great-designer