Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- const int max_prime = 4000;
- const int max_n = 10000000;
- int n, p, ans, a[max_n];
- bool prime[max_prime];
- vector< int > d, f;
- inline void read(int &n) {
- n = 0;
- char c = getchar();
- while (!isdigit(c))
- c = getchar();
- while (isdigit(c)) {
- n = (n << 3) + (n << 1) + c - '0';
- c = getchar();
- }
- }
- void recurse(int i, int v) {
- if (i == f.size()) {
- if (n / v > (v - 1) / 2) {
- ans++;
- }
- int s = p * v;
- if ((double)n / s > (double)(s - 1) / 2.00)
- ans++;
- return;
- }
- if (n / v < (v - 1) / 2)
- return;
- int num = 1;
- for (int r = 0;r <= a[f[i]];r++) {
- recurse(i + 1, v * num);
- num *= f[i];
- }
- }
- int main() {
- for (int i = 3;i < max_prime;i += 2)
- prime[i] = true;
- prime[2] = true;
- for (int i = 3;i < max_prime;i += 2) {
- if (prime[i]) {
- d.push_back(i);
- for (int j = i * i;j < max_prime;j += i) {
- prime[j] = false;
- }
- }
- }
- for (int testID = 1;;testID++) {
- ans = 0;
- read(n);
- if (n == 0)
- break;
- if (n == 1) {
- printf("2\n");
- continue;
- }
- int t = n;
- p = 2;
- f.clear();
- if (t % 2 == 0) {
- a[2] = 0;
- f.push_back(2);
- while (t % 2 == 0) {
- a[2]++;
- p *= 2;
- t /= 2;
- }
- }
- for (int i = 0;d[i] * d[i] <= t && t > 1;i++) {
- if (t % d[i] == 0) {
- a[d[i]] = 0;
- f.push_back(d[i]);
- while (t % d[i] == 0) {
- a[d[i]]++;
- t /= d[i];
- }
- }
- }
- if (t > 1) {
- f.push_back(t);
- a[t] = 1;
- }
- recurse((f[0] == 2), 1);
- printf("%d\n", ans * 2);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement