首页 > 其他 > 详细

POJ 1284 Primitive Roots (求原根个数)

时间:2014-07-30 20:43:34      阅读:396      评论:0      收藏:0      [点我收藏+]

Primitive Roots


利用定理:素数 P 的原根的个数为euler(p - 1)

typedef long long ll;
using namespace std;
/*
    求原根
    g^d ≡ 1(mod p) 其中d最小为p-1,g 便是一个原根
    复杂度:O(m)*log(P-1)(m为p-1的质因子个数)
*/
ll euler(ll x) {
    ll res = x;
    for (ll i = 2; i <= x / i; i++) if (x % i == 0) {
        res = res / i * (i - 1);
        while(x % i == 0) x /= i;
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
int main () {
    ll n;
    while(~scanf("%lld", &n)) {
        printf("%lld\n", euler(n - 1));
    }
    return 0;
}


POJ 1284 Primitive Roots (求原根个数),布布扣,bubuko.com

POJ 1284 Primitive Roots (求原根个数)

原文:http://blog.csdn.net/sio__five/article/details/38306269

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!