解题思路

本题要求对于给定的奇质数$p$（$3 \leq p < 65536$），输出模$p$的原根的个数。

1. 素数筛选：通过sieve函数利用埃拉托斯特尼筛法对$1$到$65536$范围内的数进行筛选，标记出非素数（is_prime数组中值为$1$表示非素数 ）。这样做是为了后续判断输入的数是否为素数，若不是素数直接输出$0$（因为题目要求是奇质数 ）。
2. 欧拉函数打表：phi函数用于计算$1$到$65536$范围内每个数的欧拉函数值并打表存储在euler数组中。欧拉函数$\varphi(n)$表示小于等于$n$且与$n$互质的正整数的个数。在这里用到的关键性质是：对于奇质数$p$，模$p$的原根个数等于$\varphi(p - 1)$ 。
3. 主程序处理：在main函数中，先调用上述两个函数进行初始化。然后不断读取输入的数$p$，判断若$p$不是素数则输出$0$；若是素数，则根据欧拉函数的性质，直接输出euler[p - 1]，即模$p$的原根的个数。 原根的定义：摘自百度百科

原根是一种数学符号，设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）

假设一个数g是P的原根，那么g^i mod P的结果两两不同，且有 1<g<P，0<i<P，归根到底就是g^(P-1) = 1 (mod P)当且仅当指数为P-1的时候成立.(这里P是素数)。

简单来说，g^i mod p ≠ g^j mod p （p为素数），其中i≠j且i, j介于1至(p-1)之间，则g为p的原根。

求原根目前的做法只能是从2开始枚举，然后暴力判断g^(P-1) = 1 (mod P)是否当且仅当指数为P-1的时候成立。而由于原根一般都不大，所以可以暴力得到。

根据加粗的话，可以看出来题目就是让求原根的个数

另外：阶的定义

对于素质数p：原根个数是φ(φ(p))，又因为p是质数，φ(p)=p-1，所以原根个数为φ(p-1)

对于合数以及2：原根个数为0

#include<iostream>
using namespace std;

int oula[65537];

int caoula(int n){
    if(oula[n]>0) return oula[n];
    int res = 1;
    for(int i = 2; i*i <= n; i++)
            if(n%i==0){
                       n/=i;
                       res*=(i-1);
                       while(n%i==0){
                                     n/=i;
                                     res*=i-1;
                       }
            }
    
    if(n>1) res*=n-1;
    return oula[n] = res;
}


int main(){
    int n;
    while(cin>>n)
                 cout << caoula(n-1) << endl;
}