Advertisement
Guest User

Untitled

a guest
May 26th, 2017
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int max_prime = 4000;
  8. const int max_n = 10000000;
  9.  
  10. int n, p, ans, a[max_n];
  11. bool prime[max_prime];
  12. vector< int > d, f;
  13.  
  14. inline void read(int &n) {
  15.     n = 0;
  16.     char c = getchar();
  17.     while (!isdigit(c))
  18.         c = getchar();
  19.     while (isdigit(c)) {
  20.         n = (n << 3) + (n << 1) + c - '0';
  21.         c = getchar();
  22.     }
  23. }
  24.  
  25. void recurse(int i, int v) {
  26.     if (i == f.size()) {
  27.         if (n / v > (v - 1) / 2) {
  28.             ans++;
  29.         }
  30.         int s = p * v;
  31.         if ((double)n / s > (double)(s - 1) / 2.00)
  32.             ans++;
  33.         return;
  34.     }
  35.     if (n / v < (v - 1) / 2)
  36.         return;
  37.     int num = 1;
  38.     for (int r = 0;r <= a[f[i]];r++) {
  39.         recurse(i + 1, v * num);
  40.         num *= f[i];
  41.     }
  42. }
  43.  
  44. int main() {
  45.     for (int i = 3;i < max_prime;i += 2)
  46.         prime[i] = true;
  47.     prime[2] = true;
  48.     for (int i = 3;i < max_prime;i += 2) {
  49.         if (prime[i]) {
  50.             d.push_back(i);
  51.             for (int j = i * i;j < max_prime;j += i) {
  52.                 prime[j] = false;
  53.             }
  54.         }
  55.     }
  56.     for (int testID = 1;;testID++) {
  57.         ans = 0;
  58.         read(n);
  59.         if (n == 0)
  60.             break;
  61.         if (n == 1) {
  62.             printf("2\n");
  63.             continue;
  64.         }
  65.         int t = n;
  66.         p = 2;
  67.         f.clear();
  68.         if (t % 2 == 0) {
  69.             a[2] = 0;
  70.             f.push_back(2);
  71.             while (t % 2 == 0) {
  72.                 a[2]++;
  73.                 p *= 2;
  74.                 t /= 2;
  75.             }
  76.         }
  77.         for (int i = 0;d[i] * d[i] <= t && t > 1;i++) {
  78.             if (t % d[i] == 0) {
  79.                 a[d[i]] = 0;
  80.                 f.push_back(d[i]);
  81.                 while (t % d[i] == 0) {
  82.                     a[d[i]]++;
  83.                     t /= d[i];
  84.                 }
  85.             }
  86.         }
  87.         if (t > 1) {
  88.             f.push_back(t);
  89.             a[t] = 1;
  90.         }
  91.         recurse((f[0] == 2), 1);
  92.         printf("%d\n", ans * 2);
  93.     }
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement