Originally thought it was a single stroke drawing, but it completely isn't...
Because you have to visit all the points and each step is the same length, the number of steps must be coprime with the total number of points.
Otherwise, if the greatest common divisor is not 1, it means you will finish before reaching n steps.
It is actually Euler's formula.
Extract all the prime factors of n: a1, a2, a3.
And use the formula n2=n(1-1/a1)(1-1/a2)(1-1/a3).
This is equivalent to removing all multiples of the prime factors and taking the remaining numbers.
//============================================================================
// Name : stars2.cpp
// Date : 2013/3/22 上午11:47:39
// Author : GCA
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp[htx][hty]);}Pln();}
#define M 10000000
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define Is_debug true
#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
int n;
vector<int> a;
void solve(){
int on=n;
int sqrtn=sqrt(n);
for(int i=2;i<=sqrtn;i++){
if(!(n%i)){
while(!(n%i)) n/=i;
a.PB(i);
}
}
if(n!=1)a.PB(n);
int size=a.size();
for(int i=0;i<size;i++){
// debug("%d\\n",a[i]);
on=on-on/a[i];
}
printf("%d\\n",on>>1);
}
int main() {
ios_base::sync_with_stdio(0);
while(~scanf("%d",&n)){
solve();
a.clear();
}
}