1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;

const int MAXN=1e6;
int E[MAXN+1];

vector<pair<int,int> > factor(int a){
	vector<int> f;
	vector<pair<int,int> > t;

	if(a == 1)
		return t;

	for(int i=2;i*i<=a && i*i > 0 && a > MAXN;i++)
		while(a%i == 0){
			f.push_back(i);
			a /= i;
		}

	while(a > 1 && a <= MAXN){
		f.push_back(E[a]);
		a /= E[a];
	}

	if(a != 1)
		f.push_back(a);

	sort(f.begin(), f.end());

	t.push_back({f[0],0});
	for(int i=0;i<f.size();i++){
		if(f[i] != t.back().first)
			t.push_back({f[i],0});
		t.back().second++;
	}

	return t;
}

void generate(vector<pair<int,int> >& t, vector<int>& res, int p=0, int r=1){
	if(p == t.size()){
		res.push_back(r);
		return;
	}

	for(int i=0;i<=t[p].second;i++){
		generate(t,res,p+1,r);
		r *= t[p].first;
	}
}

int calc(int n){
	vector<pair<int,int> > f = factor(n);
	for(auto& i : f)
		i.second = 1;

	vector<int> g;
	generate(f,g);
	int res=0;

	for(int i : g){
		if(i == 1)
			continue;

		lld m = n;
		while(m%i == 0)
			m /= i;

		lld t = i;
		while(t+1 < m)
			t *= i;

		if(t+1 == m)
			res++;
	}

	return res;
}

int main(void){
	ios_base::sync_with_stdio(false);

	for(int i=2;i<=MAXN;i++)
		if(E[i] == 0)
			for(int j=i;j<=MAXN;j+=i)
				E[j] = i;

	int n;
	cin >> n;

	vector<pair<int,int> > t = factor(n);
	vector<int> gen;
	generate(t,gen);

	sort(gen.begin(), gen.end());
	gen.pop_back();

	int res=0;
	for(int i : gen)
		res += calc(n/i-1);

	cout << res << "\n";

	return 0;
}