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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX_INPUT 1001001001

//#define DEBUG

using namespace std;

class sieve {
	private:
		const int MAX_SQRT;
		vector<bool> is_prime;
		
	public:
		sieve();
		vector<int> get_divisors(int n);
		
};

void print(const vector<int>&);

int main(int argc, char** argv) {
	int result = 0;
	
	int n;
	cin >> n;
	
	sieve my_sieve;
	
	
	vector<int> n_divisors = my_sieve.get_divisors(n);
	
#ifdef DEBUG
	print(n_divisors);
#endif
	
	for(int i=0 ; i<n_divisors.size() ; i++)
	{
		int shrinked = n / n_divisors[i] - 1;
		
		vector<int> shrinked_divisors = my_sieve.get_divisors(shrinked);
		
#ifdef DEBUG
		print(shrinked_divisors);
#endif
		
		for( int j=0 ; j<shrinked_divisors.size() ; j++)
		{
			if( shrinked_divisors[j]==1 )
			{
				continue;
			}
			if( shrinked_divisors[j] >= shrinked-shrinked_divisors[j] )
			{
				break;
			}
			result ++ ;
		}
	}
	cout << result << endl;
	return 0;
}

sieve::sieve() : MAX_SQRT(sqrt(MAX_INPUT)), is_prime(sqrt(MAX_INPUT), true)
{
	for(int i=2 ; i<MAX_SQRT ; i++)
	{
		if( !is_prime[i] )
		{
			continue;
		}
		for(int j=2 ; i*j<MAX_SQRT ; j++)
		{
			is_prime[i*j] = false;
		}
	}
}

vector<int> sieve::get_divisors(int n)
{
	vector<int> divisors;
	
	for(int i=1 ; i<n ; i++)
	{
		if(i*i > n)
		{
			break;
		}
		if(n%i != 0)
		{
			continue;
		}
		divisors.push_back(i);
	}
	
	int max_so_far = 1;
	if(divisors.size()>0)
	{
		max_so_far = divisors.back();
	}
	
	for(int i=divisors.size()-1 ; i>=0 ; i--)
	{
		int other = n/divisors[i];
		if(max_so_far >= other)
		{
			continue;
		}
		else
		{
			divisors.push_back(other);
			max_so_far = other;
		}
	}
	
	return divisors;
}

void print(const vector<int>& v)
{
	for(int i=0 ; i<v.size() ; i++)
	{
		cout << v[i] << " "; 
	}
	cout << "\n";
}