diff options
| author | mzuenni <mzuenni@users.noreply.github.com> | 2024-07-28 22:54:40 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-07-28 22:54:40 +0200 |
| commit | 8d11c6c8213f46f0fa19826917c255edd5d43cb1 (patch) | |
| tree | 96d75baff33d5a04b5a60f1a41f514a26c716874 /content/math/squfof.cpp | |
| parent | 8c33b4e0d3030cfed17fc64b4fe41133339f6d87 (diff) | |
Test (#4)
* update
* moved content in subdir
* rename file
* add test setup
* add test setup
* add github action
* automaticly test all cpp files
* timeout after 10s
* setulimit and dont zero memory
* test build pdf
* install latexmk
* update
* update
* ngerman
* fonts
* removed old code
* add first test
* added tests
* test in sorted order
* more tests
* simplified test
* more tests
* fix suffix tree
* fixes and improvements
* done ust lst directly
* fix swap
* add links to pdf
* fix constants
* add primorial
* add comment
* various improvements
* more tests
* added missing stuf
* more tests
* fix tests
* more tests
* more tests
* more tests
* fix recursion?
* test trie
* more tests
* only use python temporarily for listings
* only use python temporarily for listings
* more tests
* fix longestCommonSubstring
* more tests
* more tests
* made code more similiar
* fix?
* more tests
* more tests
* more tests
* add ahoCorasick test + limit 4GB stack size
* more tests
* fix test
* add additional test
* more tests
* more tests
* fix?
* better fix
* fix virtual tree
* more tests
* more tests
* recursive closest pair
* more tests
* decrease limit
* new tests
* more tests
* fix name
* more tests
* add test
* new test
* more tests
* more tests
* more tests
* more tests
* new test and content
* new code
* new code
* larger tests
* fix and test
* new test
* new test
* update pdf
* remove comments
* new test
* more tests
* more testcases
* more tests
* increased limit
* more tests
* more tests
* more tests
* new tests
* more tests
* shortened code
* new test
* add basic tests for bigint
* more tests
* removed old files
* new test
* ignore some files
* more auto more ccw
* fix test
* more tests
* fix
* new tests
* more tests
* more tests
* stronger test
* actually verify delaunay...
* more tests
* fix header
* more tests
* run tests parallel?
* test parralel?
* add --missing
* separate workflows
* test
* is the pdf checked?
* separate workflows
* fix workflow
* more workflows
---------
Co-authored-by: Yidi <noob999noob999@gmail.com>
Diffstat (limited to 'content/math/squfof.cpp')
| -rw-r--r-- | content/math/squfof.cpp | 89 |
1 files changed, 89 insertions, 0 deletions
diff --git a/content/math/squfof.cpp b/content/math/squfof.cpp new file mode 100644 index 0000000..1cb97de --- /dev/null +++ b/content/math/squfof.cpp @@ -0,0 +1,89 @@ +using lll = __int128;
+
+constexpr lll multipliers[] = {1, 3, 5, 7,
+ 11, 3*5, 3*7, 3*11,
+ 5*7, 5*11, 7*11,
+ 3*5*7, 3*5*11, 3*7*11,
+ 5*7*11, 3*5*7*11};
+
+lll root(lll x) {
+ lll r = sqrtl(x);
+ while(r*r < x) r++;
+ while(r*r > x) r--;
+ return r;
+}
+
+lll croot(lll x) {
+ lll r = cbrtl(x);
+ while(r*r*r < x) r++;
+ while(r*r*r > x) r--;
+ return r;
+}
+
+lll squfof(lll N) {
+ lll s = croot(N);
+ if (s*s*s == N) return s;
+ s = root(N);
+ if (s*s == N) return s;
+ for (lll k : multipliers) {
+ lll D = k * N;
+ lll Po, P, Pprev, q, b, r, i;
+ Po = Pprev = P = root(D);
+ lll Qprev = 1;
+ lll Q = D - Po*Po;
+ lll L = 2 * root(2 * s);
+ lll B = 3 * L;
+ for (i = 2; i < B; i++) {
+ b = (Po + P) / Q;
+ P = b*Q - P;
+ q = Q;
+ Q = Qprev + b * (Pprev - P);
+ r = root(Q);
+ if (!(i & 1) && r*r == Q) break;
+ Qprev = q;
+ Pprev = P;
+ }
+ if (i >= B) continue;
+ b = (Po - P) / r;
+ Pprev = P = b*r + P;
+ Qprev = r;
+ Q = (D-Pprev*Pprev)/Qprev;
+ i = 0;
+ do {
+ b = (Po + P) / Q;
+ Pprev = P;
+ P = b*Q - P;
+ q = Q;
+ Q = Qprev + b * (Pprev - P);
+ Qprev = q;
+ i++;
+ } while(P != Pprev);
+ r = gcd(N, Qprev);
+ if (r != 1 && r != N) return r;
+ }
+ exit(1);//try fallback to pollard rho
+}
+
+constexpr lll trialLim = 5'000;
+
+void factor(lll n, map<lll, int>& facts) {
+ for (lll i = 2; i * i <= n && i <= trialLim; i++) {
+ while (n % i == 0) {
+ facts[i]++;
+ n /= i;
+ }}
+ if (n > 1 && n < trialLim * trialLim) {
+ facts[n]++;
+ } else {
+ vector<lll> todo = {n};
+ while (!todo.empty()) {
+ lll c = todo.back();
+ todo.pop_back();
+ if (c == 1) continue;
+ if (isPrime(c)) {
+ facts[c]++;
+ } else {
+ lll d = squfof(c);
+ todo.push_back(d);
+ todo.push_back(c / d);
+}}}}
|