51nod 1135 原根

定义:,使得成立的最小的,称为对模的阶,记为

定理:如果模有原根,那么它一共有个原根。

定理:,则

定理:如果为素数,那么素数一定存在原根,并且模的原根的个数为

定理:是正整数,是整数,若的阶等于,则称为模的一个原根。

假设一个数对于模来说是原根,那么的结果两两不同,且有,那么可以称为是模的一个原根,归根到底就是当且仅当指数为的时候成立。(这里是素数)

有原根的充要条件:,其中是奇素数。

求模素数原根的方法:素因子分解,即的标准分解式,若恒有

成立,则就是的原根。(对于合数求原根,只需把换成即可)

#include <iostream>
#include <stdio.h>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
long long d[1000];
long long dp[1000];
int kuai(long long x,long long n,long long m)
{
    long long i,j;
    long long s=1;
    for(i=0;;i++)
    {

        long long t=x;
        long long d=n%2;n=n/2;
        if(d==0) t=1;
        if(d!=0)
        {
            if(i==0) t=t*1%m;
            else
            {
                for(j=0;j<i;j++)
                t=t*t%m;
            }
        }
        s=s*t%m; if(n==0) break;
    }
    return s;
}
int main()
{
    long long p;
    while(cin>>p)
    {
        long long k=p-1;
        long long i;
        long long x=1;
        d[0]=k;
        d[1]=1;
        if(k%2==0)
        {
            d[2]=2;
            while(k%2==0) k=k/2;
        }
        long long l=3;
        for(long long j=3;j<=k;j+=2)
        {
            if(k%j==0)
            {
                d[l]=j;l++;
                while(k%j==0) k=k/j;
               //cout<<j<<endl;
            }
        }

        for(i=2;i<=p;i++)
        {
            long long z=1;
            for(long long j=2;j<l;j++)
            {
                long long t=(p-1)/d[j];

                long long r=kuai(i,t,p);
                //cout<<r<<' '<<t<<' '<<d[j]<<' '<<i<<endl;
                if(r==1) {z=0;break;}

            }

            if(z==1) {cout<<i<<endl;break;}
        }
    }
}
时间: 07-14

51nod 1135 原根的相关文章

求最小原根 51nod 1135

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135 代码 // the smallest primitive root of prime P #include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using namespace std; long long N; i

原根(扩展欧几里得+欧拉函数)

1135 原根 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根.(其中φ(m)表示m的欧拉函数) 给出1个质数P,找出P最小的原根. Input 输入1个质数P(3 <= P <= 10^9) Output 输出P最小的原根. Input示例 3 Output示例 2 转载请注明出处:寻找&星空の孩子 题目链接:http://www.51nod.com/onlineJudge/que

51nod1135(求最小原根)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135 题意:中文题诶- 思路:设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根.(其中φ(m)表示m的欧拉函数)给出1个质数P,找出P最小的原根. 我们先了解一下阶的概念:满足 a^r Ξ (1 mod m) ---1 的最小 r 即为 a%m的阶,我们可以直接从小到大枚举a, 然后将 r= φ(m) 带入进去, 判断如果满足  1式

51nod 1201 整数划分(dp)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1201 题解:显然是一道dp,不妨设dp[i][j]表示数字i分成j个一共有几种分法. 那么转移方程式为: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] 表示将i - 1划分为j个数,然后j个数都+1 还是不重复,将i - 1划分为j - 1个数,然后j - 1个数都+1,再加上1这个数. 然后就是j的范围要知道1+2+

51nod 1138 连续整数的和(数学)

题目描述: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1138 给出一个正整数N,将N写为若干个连续数字和的形式(长度 >= 2).例如N = 15,可以写为1 + 2 + 3 + 4 + 5,也可以写为4 + 5 + 6,或7 + 8.如果不能写为若干个连续整数的和,则输出No Solution. Input 输入1个数N(3 <= N <= 10^9). OutPut 输出连续整数中的第1个数,如果有多

51nod 1463 找朋友(线段树+离线处理)

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1463 题意: 思路: 好题! 先对所有查询进行离线处理,按照右区间排序,因为k一共最多只有10个,所有在该区间内的B数组,每次枚举K值,通过这样的方式来得到另外一个B值.但是这样得到的B值它在B数组中的位置必须在当前数的左边.如下图:(j为当前数在B数组中的位置,pos为计算得到的另一个B值在数组中的位置) 这两个数的和记录在pos中,这里pos的位置必须在j的左边,假

51nod 1437

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1437 1437 迈克步 题目来源: CodeForces 基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 收藏 关注 有n只熊.他们站成一排队伍,从左到右依次1到n编号.第i只熊的高度是ai. 一组熊指的队伍中连续的一个子段.组的大小就是熊的数目.而组的力量就是这一组熊中最小的高度. 迈克想知道对于所有的组大小为x(1 ≤ x ≤ n

51nod 1272 思维/线段树

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1272 1272 最大距离 题目来源: Codility 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 收藏 关注 给出一个长度为N的整数数组A,对于每一个数组元素,如果他后面存在大于等于该元素的数,则这两个数可以组成一对.每个元素和自己也可以组成一对.例如:{5, 3, 6, 3, 4, 2},可以组成11对,如下(数字为下标):

51nod 1406 位运算/dp

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1406 1406 与查询 题目来源: CodeForces 基准时间限制:2 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 收藏 关注 有n个整数.输出他之中和x相与之后结果为x的有多少个.x从0到1,000,000 Input 第一行输入一个整数n.(1<=n<=1,000,000). 第二行有n个整数a[0],a[1],a[2],...a[n-1