We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Mathematics
  3. Number Theory
  4. Primitive Problem
  5. Discussions

Primitive Problem

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 880 Discussions, By:

votes

Please Login in order to post a comment

  • Sanjit_Prasad
    4 years ago+ 19 comments

    THIS PROBLEM MADE ME QUESTION MY EXISTENCE :(

    19|
    Permalink
    View more Comments..
  • weskerhluffy
    2 years ago+ 3 comments

    This video explains very well the primitive root topic and how to calculate the number of primitive roots https://www.youtube.com/watch?v=IviYLdqmIdw&t=6s . P.S.: There are a lot of spam in this discussion

    10|
    Permalink
  • subhajit104
    3 years ago+ 3 comments

    algo: 1. find all the unique prime factor of the n-1.

    ll number = n-1 ; 
        vector<ll> fact;
        for(ll i = 2 ; i*i <= number ; i++){ // O(n)
            if( number%i == 0 )
                fact.push_back(i);
            while(number%i == 0)
                number /= i;
        }
        if(number > 2)
            fact.push_back(number);
    
    1. then find the smallest primitive root using the giving link in the editorial.
    ll s_primitive;
        for(ll i = 2 ; i < n ; i++){
            bool flag = true;
            for(auto prime: fact){
                if(power(i,n/prime,n) == 1){
                    flag = false;
                    break;
                }
            }
            if(flag){ 
                    s_primitive = i;
                    break;
                }
        }
        cout << s_primitive << " ";
    
    1. find the number of the primitove roots. We know that any prime p has ϕ(p−1) primitive roots. We also know that the prime power decomposition of p - 1 can be written as: p−1=p1^(e1),p2^(e2)..., and we then know that ϕ(p−1)=p1^(e1−1)(p1−1)p2^(e2−1)(p2−1)...pk^(ek−1)*(pk−1)
    n--;
        for(auto fa:fact)
            n = n/fa*(fa-1);
        cout << n << endl;
    
    7|
    Permalink
  • subhajit104
    3 years ago+ 3 comments
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long int
    ll n , s_primitive,number;
    
    ll power(ll a, ll b, ll mod){
        if(b == 0)
            return 1;
        ll temp = power(a,b>>1,mod)%mod;
        temp = (temp*temp)%mod;
        if(b&1)
            temp = temp*a%mod;
        return temp;
    }
    
    5|
    Permalink
  • fcong1989
    1 year ago+ 0 comments

    I think this coding test is left by the website manager in the forgotten corner. Why do I say this?

    First of all, the editorial is not as informative as for others. So I need to really check wikipedia and search for what I could really use.

    Secondly, the forum is full of advertisements, perhaps providing virus links. I think all those comments should be removed.

    Back to the problem itself, here are some "more detailed" hints from me:

    1. Use the information from the Math StackExchange website. It helps to reduce the test cases you need to try for each number g. To be concrete, instead of trying all the powers from 0 to p-2, you can simply try the numbers , where denotes the ith distince prime factor of p-1. This can significantly reduce the computation load.

    2. when you calcualate the Euler totient function of p-1, you can use the formula: , where denotes the ith distince prime factor of x. This is also known as "the Euler product formula". You can find it in the wikipedia page.

    4|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature