Competitive Programming Solutions

284A - Cows And Primitive Roots

26 Dec 2020 — Tags: brute_force,modulo — URL

Brute force and test all $x < p$. Check this editorial for a more mathy solution.

Time complexity: $O(p^2)$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(int p)
{
    int ans = 0;
    for (int x = 1; x < p; ++x)
    {
        bool flag = true;
        int y = x % p;
        for (int i = 1; i <= p - 2; ++i)
        {
            if (y == 1)
            {
                flag = false;
                break;
            }
            y = (y * x) % p;
        }
        if (y % p != 1)
            flag = false;
        ans += flag;
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int p;
    cin >> p;
    cout << solve(p) << endl;
    return 0;
}

Related posts