fix a bug on primitive-root

zimpha · zimpha · commit a3b98a0a9542 · 2016-09-19T00:32:39.000+08:00
diff --git a/mathematics/primitive-root.cc b/mathematics/primitive-root.cc
@@ -7,15 +7,15 @@ bool test(LL g, LL n, LL phi, std::vector<LL> &u) {
   return true;
 }
 LL primitive_root(LL n) {
-  LL phi = euler_phi(n), m = n;
+  LL phi = euler_phi(n), m = phi;
   std::vector<LL> u;
-  for (LL i = 2; i * i <= m; ++i) if (n % i == 0) {
+  for (LL i = 2; i * i <= m; ++i) if (m % i == 0) {
     u.push_back(i);
-    while (n % i == 0) n /= i;
+    while (m % i == 0) m /= i;
   }
-  if (n > 1) u.push_back(n);
+  if (m > 1) u.push_back(m);
   for (int g = 1; ; ++g) {
-    if (test(g, m, phi, u)) return g;
+    if (test(g, n, phi, u)) return g;
   }
   return -1;
 }

Original file line number	Diff line number	Diff line change
`@@ -7,15 +7,15 @@ bool test(LL g, LL n, LL phi, std::vector<LL> &u) {`
`7`	`7`	`return true;`
`8`	`8`	`}`
`9`	`9`	`LL primitive_root(LL n) {`
`10`		`- LL phi = euler_phi(n), m = n;`
	`10`	`+ LL phi = euler_phi(n), m = phi;`
`11`	`11`	`std::vector<LL> u;`
`12`		`- for (LL i = 2; i * i <= m; ++i) if (n % i == 0) {`
	`12`	`+ for (LL i = 2; i * i <= m; ++i) if (m % i == 0) {`
`13`	`13`	`u.push_back(i);`
`14`		`- while (n % i == 0) n /= i;`
	`14`	`+ while (m % i == 0) m /= i;`
`15`	`15`	`}`
`16`		`- if (n > 1) u.push_back(n);`
	`16`	`+ if (m > 1) u.push_back(m);`
`17`	`17`	`for (int g = 1; ; ++g) {`
`18`		`- if (test(g, m, phi, u)) return g;`
	`18`	`+ if (test(g, n, phi, u)) return g;`
`19`	`19`	`}`
`20`	`20`	`return -1;`
`21`	`21`	`}`