| 1 | #include "mod_pow.cpp" |
| 2 | ll primitive_root(ll m) { |
| 3 | vector<ll> div; |
| 4 | for (ll i = 1; i*i <= m-1; i++) { |
| 5 | if ((m-1) % i == 0) { |
| 6 | if (i < m) div.push_back(i); |
| 7 | if (m/i < m) div.push_back(m/i); } } |
| 8 | rep(x,2,m) { |
| 9 | bool ok = true; |
| 10 | iter(it,div) if (mod_pow<ll>(x, *it, m) == 1) { |
| 11 | ok = false; break; } |
| 12 | if (ok) return x; } |
| 13 | return -1; } |
| 14 | // vim: cc=60 ts=2 sts=2 sw=2: |