51nod1135 原根+模板

2019-04-14 17:18发布

站内文章 / 模拟电子
12856 0 1625
设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。 a^r ≡ 1(mod m)  最小的一个r就是a模m的阶。 假如m是素数a^(m-1) ≡ 1 (mod m) 当且仅当指数为m-1时成立，a就是m的原根。 (a^i)%m两两不同(0 <= i < p, 1 < a < p), a就是m的原根。 假如m有原根那么它一共有φ(φ(m))个原根。 求素数原根的方法:对p-1质因子分解p-1 = p1^a1 * p2^a2 * p3^a3...若恒有a^((p-1)/pi) ≠ 1(mod p)成立那么a就是p的原根（对于合数求原根，只需要把p-1换成φ(p)即可）   #include using namespace std; typedef long long ll; const int maxn = 1e5 + 5; ll qpow(ll a, ll b, ll m) {ll ans = 1;while(b) {if(b % 2) ans = ans * a % m;a = a * a % m;b >>= 1;}return ans % m;} ll factor[maxn], k = 0; void decompose(ll x) {//分解质因子 ll ans = 0; for (ll i = 2; i * i <= x; i++) { if (x % i == 0) { factor[k++] = i; while (x % i == 0) x /= i; } } if (x > 1) factor[k++] = x; } ll cal(ll n) {//求素数最小原根 decompose(n - 1); for (ll g = 2; g < n; g++) { int flag = 1; for (int i = 0; i < k; i++) { ll t = (n - 1) / factor[i]; if (qpow(g, t, n) == 1) { flag = 0; break; } } if (flag == 1) return g; } } int main() { ll n; scanf("%lld", &n); ll ans = cal(n); printf("%lld ", ans); return 0; }  

热门文章