// Author: Piotr Grzegorczyk (ud2@interia.eu) // Task: PA2018/PIN #include <bits/stdc++.h> using namespace std; vector<int> vp; void prime_init(int N) { int sn = 1 + (int)sqrt(N); vector<int> s(sn, 0); for (int d=1; d<sn; d++) for (int i=d; i<sn; i+=d) s[i]++; for (int i=2; i<sn; i++) if (s[i]==2) vp.push_back(i); } vector<int> divisors(int N) { vector<int> vd; vd.push_back(1); int n = N; for (int i=0; i<vp.size() && 1ll*vp[i]*vp[i] <= n; i++) { int u = 0; int v = vd.size(); while (n % vp[i]==0) { for (int j=u; j<v; j++) vd.push_back(vd[j] * vp[i]); u = v; v = vd.size(); n /= vp[i]; } } if (n > 1) { int v = vd.size(); for (int j=0; j<v; j++) vd.push_back(vd[j] * n); } // sort(vd.begin(), vd.end()); return move(vd); } int solve(int n) { int r = 0; vector<int> vd1 = move( divisors(n) ); for (int i=0; i<vd1.size(); i++) { int a = vd1[i]; int d = n/a - 1; if (d < 1) continue; vector<int> vd2 = move( divisors(d) ); for (int j=0; j<vd2.size(); j++) { int p = vd2[j]; int q = d/p - 1; if (p<2 || q<2) continue; /* int b = a*p; int c = b*q; fprintf(stderr, "1: (%lld %lld %lld)\n", a, b, c); */ r++; } } return r; } int main() { prime_init(1E9); int n = 35; scanf("%d", &n); printf("%d\n", solve(n)); 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 | // Author: Piotr Grzegorczyk (ud2@interia.eu) // Task: PA2018/PIN #include <bits/stdc++.h> using namespace std; vector<int> vp; void prime_init(int N) { int sn = 1 + (int)sqrt(N); vector<int> s(sn, 0); for (int d=1; d<sn; d++) for (int i=d; i<sn; i+=d) s[i]++; for (int i=2; i<sn; i++) if (s[i]==2) vp.push_back(i); } vector<int> divisors(int N) { vector<int> vd; vd.push_back(1); int n = N; for (int i=0; i<vp.size() && 1ll*vp[i]*vp[i] <= n; i++) { int u = 0; int v = vd.size(); while (n % vp[i]==0) { for (int j=u; j<v; j++) vd.push_back(vd[j] * vp[i]); u = v; v = vd.size(); n /= vp[i]; } } if (n > 1) { int v = vd.size(); for (int j=0; j<v; j++) vd.push_back(vd[j] * n); } // sort(vd.begin(), vd.end()); return move(vd); } int solve(int n) { int r = 0; vector<int> vd1 = move( divisors(n) ); for (int i=0; i<vd1.size(); i++) { int a = vd1[i]; int d = n/a - 1; if (d < 1) continue; vector<int> vd2 = move( divisors(d) ); for (int j=0; j<vd2.size(); j++) { int p = vd2[j]; int q = d/p - 1; if (p<2 || q<2) continue; /* int b = a*p; int c = b*q; fprintf(stderr, "1: (%lld %lld %lld)\n", a, b, c); */ r++; } } return r; } int main() { prime_init(1E9); int n = 35; scanf("%d", &n); printf("%d\n", solve(n)); return 0; } |