#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <set> #include <vector> using namespace std; #define REP(i, n) for (int i = 0; i < (int)n; i++) #define ST first #define ND second #define MP make_pair #define PB push_back typedef vector<int> VI; typedef pair<int, int> PI; typedef vector<PI> VPII; typedef set<int> SI; typedef long long LL; #ifdef DEBUG const bool debug = true; #else const bool debug = false; #endif int n, m, k, l, test = 1; const int INF = 1000 * 1000 * 1000; const int MAKSN = 1000 * 1000 + 13; // UZUPElnic void readIn() { cin >> n; } VI divList(int num) { VI dziel; for (int i = 1; i * i <= num; i++) { if (num % i == 0) { dziel.push_back(i); if (i * i != num) dziel.push_back(num / i); } } sort(dziel.begin(), dziel.end()); return dziel; } // a, a * p, a * p * q; // 1, p, p * q // p, p * q // 1, q // n = a + ap + apq // n/a = 1 + p + pq // n/a - 1 = p + pq int calc(int a) { int sum = n / a; sum--; VI divs = divList(sum); int cnt = 0; for (uint i = 1; i < divs.size(); i++) { // skip 1 int cur = sum / divs[i]; cur--; if (cur > 1) { // a, a * divs[i] , a *divs[i] * cur // cerr << a << " " << a*divs[i] << " " << a * divs[i] * cur << // "\n"; // cerr << cur << " " << a << " " << sum << " " << divs[i] // <<"\n"; cnt += 1; } } return cnt; } void solve() { VI dziel = divList(n); int cnt = 0; for (uint i = 0; i < dziel.size(); i++) { // cerr << "Dziel = " << dziel[i] << "\n"; cnt += calc(dziel[i]); } cout << cnt << "\n"; } void zeruj() {} int main() { ios_base::sync_with_stdio(0); readIn(); solve(); return 0; }
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 | #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <set> #include <vector> using namespace std; #define REP(i, n) for (int i = 0; i < (int)n; i++) #define ST first #define ND second #define MP make_pair #define PB push_back typedef vector<int> VI; typedef pair<int, int> PI; typedef vector<PI> VPII; typedef set<int> SI; typedef long long LL; #ifdef DEBUG const bool debug = true; #else const bool debug = false; #endif int n, m, k, l, test = 1; const int INF = 1000 * 1000 * 1000; const int MAKSN = 1000 * 1000 + 13; // UZUPElnic void readIn() { cin >> n; } VI divList(int num) { VI dziel; for (int i = 1; i * i <= num; i++) { if (num % i == 0) { dziel.push_back(i); if (i * i != num) dziel.push_back(num / i); } } sort(dziel.begin(), dziel.end()); return dziel; } // a, a * p, a * p * q; // 1, p, p * q // p, p * q // 1, q // n = a + ap + apq // n/a = 1 + p + pq // n/a - 1 = p + pq int calc(int a) { int sum = n / a; sum--; VI divs = divList(sum); int cnt = 0; for (uint i = 1; i < divs.size(); i++) { // skip 1 int cur = sum / divs[i]; cur--; if (cur > 1) { // a, a * divs[i] , a *divs[i] * cur // cerr << a << " " << a*divs[i] << " " << a * divs[i] * cur << // "\n"; // cerr << cur << " " << a << " " << sum << " " << divs[i] // <<"\n"; cnt += 1; } } return cnt; } void solve() { VI dziel = divList(n); int cnt = 0; for (uint i = 0; i < dziel.size(); i++) { // cerr << "Dziel = " << dziel[i] << "\n"; cnt += calc(dziel[i]); } cout << cnt << "\n"; } void zeruj() {} int main() { ios_base::sync_with_stdio(0); readIn(); solve(); return 0; } |