Primitive Roots POJ - 1284（欧拉函数和原根）

Love The Way You Lie 2023-08-17 15:41 123阅读 0赞

# Primitive Roots  POJ - 1284 #

题目链接：[https://vjudge.net/problem/POJ-1284\#author=laguna][https_vjudge.net_problem_POJ-1284_author_laguna]

题目：

孤单的zydsg又一次孤单的度过了520，不过下一次不会再这样了。zydsg要做些改变，他想去和同余小姐姐约会。  
已知zydsg的号码为一个奇素数p，所有同余小姐姐的编号x都满足 0 < x < p。  
只有当x满足集合 \{ (x i mod p) | 1 <= i <= p-1 \} 等于集合\{ 1, ..., p-1 \}时，x号小姐姐才愿意与zydsg约会。例如，3 的i次方（i从1到6）模 7 的余数为 3, 2, 6, 4, 5, 1, 所以如果zydsg的号码为7的时候3号小姐姐会和他约会。  
你也看到了，zydsg的时间都拿和小姐姐们约会了，只能单身狗的你来写个代码帮他算算当他的编号为p时（p为奇素数且满足3 <= p < 65536）能和多少小姐姐约会。

Input

多组数据。每组包含一个奇素数p，代表zydsg的编号。

Output

对每个p, 输出一行，代表与能zydsg约会的小姐姐个数。

Sample Input

23
    31
    79

Sample Output

10
    8
    24
    
    思路：这题考察了两个，一个是奇素数肯定有原根，第二个是一个数n的原根的个数num=euler[euler[n]],
    又因为n为奇素数，所以euler[n]=n-1,所以n原根个数为euler[n-1],那么什么是原根呢？一个数的原根就是
    指一个小于n的正整数x,若x^1%n,x^2modn,x^3%n、、、x^n-1%n刚好是n-1的一个全排列，那么这个x就是n的一个原根。
    该题我打了欧拉值的表来做的，但是数组范围要把握好，太大会超内存，太小会RE

//
    // Created by hanyu on 2019/8/9.
    //
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int maxn=6e5+999;
    #define MAX 0x3f3f3f3f
    int euler[maxn];
    void value()
    {
        memset(euler,0,sizeof(euler));
        euler[1]=1;
        for(int i=2;i<=maxn;i++)
        {
            if(!euler[i])
            {
                for(int j=i;j<=maxn;j+=i)
                {
                    if(!euler[j])
                        euler[j]=j;
                    euler[j]=euler[j]/i*(i-1);
                }
            }
        }
    }
    int main()
    {
        int n;
        value();
        while(~scanf("%d",&n))
        {
            printf("%d\n",euler[n-1]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11328533.html

[https_vjudge.net_problem_POJ-1284_author_laguna]: https://vjudge.net/problem/POJ-1284#author=laguna