284A - Cows and Primitive Roots - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define fo(i,n) for(int i=0;i<n;i++)
#define int long long

#ifndef ONLINE_JUDGE
#define deb(x) cerr<<#x<<" "; _print(x); cerr<<'\n';
#else
#define deb(x)
#endif

void _print(float t){cerr<<t;}
void _print(double t){cerr<<t;}
void _print(int t){cerr<<t;}
void _print(string t){cerr<<t;}
void _print(char t){cerr<<t;}
//void _print(long long t){cerr<<t;}
void _print(long double t){cerr<<t;}

template<class T> void _print(vector<T> v){cerr<<"[ ";for(T i:v){cerr<<i<<" ";}cerr<<"]";}
template<class T,class V> void _print(map<T,V>m){cerr<<"[ ";for(auto it:m){cerr<<"{"<<it.first<<","<<it.second<<"} ";}cerr<<"]";}
template<class T,class V>void _print(vector<pair<T,V>>m){cerr<<"[ ";for(auto it:m){cerr<<"{"<<it.first<<" "<<it.second<<"} ";}cerr<<"]";} 
template<class T> void _print(T a[],int n){cerr<<"array:"<<" "<<"[ ";fo(i,n){cerr<<a[i]<<" ";}cerr<<"]\n";}
template<class T,class V> void _print(pair<T,V>p){cerr<<"{"<<p.first<<" "<<p.second<<"}";}
template<class T> void _print(set<T>s){cerr<<"[ ";for(auto it: s){cerr<<it<<" ";}cerr<<"]";}
template<class T> void _print(queue<T>q){queue<T>temp=q;cerr<<"[ ";while (!temp.empty()){cerr<<temp.front()<<" ";temp.pop();}cerr<<" ]";}
template<class T> void _print(priority_queue<T>q){priority_queue<T>temp=q;cerr<<"[ ";while (!temp.empty()){cerr<<temp.top()<<" ";temp.pop();}cerr<<" ]";}
template<class T> void _print(priority_queue<T,vector<T>,greater<T>>q){auto temp=q;cerr<<"[ ";while (!temp.empty()){cerr<<temp.top()<<" ";temp.pop();}cerr<<" ]";}
template<class T,class V> void _print(queue<pair<T,V>>q){queue<pair<T,V>>temp=q;cerr<<"[ ";while (!temp.empty()){cerr<<"{"<<temp.front().first<<","<<temp.front().second<<"}"<<" ";temp.pop();}cerr<<" ]";}
template<class T,class V> void _print(priority_queue<pair<T,V>>q){priority_queue<pair<T,V>>temp=q;cerr<<"[ ";while (!temp.empty()){cerr<<"{"<<temp.top().first<<","<<temp.top().second<<"}"<<" ";temp.pop();}cerr<<" ]";}
template<class T,class V> void _print(priority_queue<pair<T,V>,vector<pair<T,V>>,greater<pair<T,V>>>q){auto temp=q;cerr<<"[ ";while (!temp.empty()){cerr<<"{"<<temp.top().first<<","<<temp.top().second<<"}"<<" ";temp.pop();}cerr<<" ]";}
template<class T> void _print(deque<T>s){cerr<<"[ ";for(auto it: s){cerr<<it<<" ";}cerr<<"]";}
template<class T> void _print(vector<vector<T>>v){for(auto it : v){_print(it);cerr<<'\n';}}
template<class T,class V> void _print(unordered_map<T,V>m){cerr<<"[ ";for(auto it:m){cerr<<"{"<<it.first<<","<<it.second<<"} ";}cerr<<"]";}

/*----------------USEFUL FUNCTIONS--------------------------------------------------*/
int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
int fact(int n, int mod) {int ans{1};for(int i = 1; i <= n; i++){ans = (ans * i) % mod;}return ans;}
int C(int n, int k, int mod) {return fact(n,mod) * expo(fact(k,mod), mod - 2,mod)%mod * expo(fact(n - k,mod), mod - 2,mod)%mod;}
void sieve(int n,vector<int>&vect) {vector<int>arr(n+1,0); for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;}}
void add(int &a,int b,int m){(a+=b)%=m;}
void mul(int &a,int b,int m){(a*=b)%=m;}
void div(int &a,int b,int m){(a*=expo(b,m-2,m))%=m;}
/*-----------------------------------------------------------------------------------*/

#define vi vector<int>
#define vvi vector<vi>
#define pr pair<int,int>
#define vpr vector<pr>
#define all(v) v.begin(),v.end()
#define f first
#define sc second
#define lb lower_bound
#define ub upper_bound

void solve()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=2;i<n;i++)
    {
        for(int j=1;j<n-1;j++)
        {
            if(expo(i,j,n)==1)
            {
                ans--;
                break;
            }
        }
        ans++;
    }
    if(n==2)
        ans=1;
    cout<<ans;
}

int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("Error.txt", "w", stderr);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin >> t;
    while (t--)
        solve();
}