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.
  1. Practice
  2. Mathematics
  3. Number Theory
  4. Primitive Problem
  5. Discussions

Primitive Problem

Sort 880 Discussions, By:

  • Sanjit_Prasad
     + 19 comments

    THIS PROBLEM MADE ME QUESTION MY EXISTENCE :(

  • weskerhluffy
     + 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

  • subhajit104
     + 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;

  • subhajit104
     + 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;
}

  • fcong1989
     + 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.

Load more conversations