Find Solutions

Look at the following equation:

c = ab - + 1

Now given the value of c, how many possible values of and a and b are there (a and b must be positive integers)? That is you will have to find the number of pairs (a, b) which satisfies the above equation.

Input 

The input file contains around 3000 line of input. Each line contains an integers n ( 0 < n10¹⁴). This n actually denotes the value of c. A line containing a single zero terminates the input. This line should not be processed.

Output 

For each line of input produce one line of output. This line contains two integers. First integer denotes the value of c and the second integer denotes the number of pair of values of a and b that satisfies the above equation, given the value of c.

Sample Input 

1020
400
0

Sample Output 

1020 8
400 2

Comments: The 8 solution pairs for the first sample input are (1, 2039), (2, 680), (5, 227), (14, 76), (76, 14), (227 5), (680, 2) and (2039, 1).

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define maxL (20000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
#define LL long long
int mark[maxL] = {};
long long p[2000000], pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 20000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            p[pt++] = i;
        }
    }
}
long long cntDivisor(long long n) {
    static long long i, j, t;
    j = 1;
    for(i = 0; i < pt && p[i]*p[i] <= n; i++) {
        if(n%p[i] == 0) {
            t = 1;
            n /= p[i];
            while(n%p[i] == 0)
                n /= p[i], t++;
            j *= (t+1);
        }
    }
    if(n != 1)  j *= 2;
    return j;
}
int main() {
    sieve();
    long long c;
    while(scanf("%lld", &c) == 1 && c) {
        long long n = c*4-3;
        long long cnt;
        cnt = cntDivisor(n);
        printf("%lld %lld\n", c, cnt);
    }
    return 0;
}