Description

Find Solutions

Look at the following equation:

c = ab - + 1

Now given the value of c, how many possible values of anda and b are there (a andb 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 integersn ( 0 < n10¹⁴). Thisn 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 ofc and the second integer denotes the number of pair of values ofa and b that satisfies the above equation, given the value ofc.

Sample Input 

1020
400
0

Sample Output 

1020 8
400 2题意：求等式是c的所有可能
思路：将c=a?b?a+b2+1  因式分解后得到4?c?3=(2?a?1)?(2?b?1)
所以这道题目就可以转换为求4*c-3的因数的组成了，在求出所有的因子的质数后，就是用隔板法将f[i]拆成2个,就是乘以f[i]+1.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 22000000;

int f[maxn], b[maxn];
int lp, p[maxn>>3], pri[maxn];

void init() { // pri[] 最小的因子
	lp = 0;
	for (int i = 2; i < maxn; i++) {
		if (!pri[i])
			p[lp++] = pri[i] = i;
		for (int j = 0; j < lp && i * p[j] < maxn; j++) {
			pri[i * p[j]] = p[j];
			if (i % p[j] == 0)
				break;
		}
	}
}

void cal(ll n, ll &l, int b[], int f[]) {
	ll tmp, i = 0;
	l = 0;
	while (n > 1) {
		if (n < maxn)
			tmp = pri[n];
		else {
			tmp = n;
			for (; i < lp && n/p[i] >= p[i]; i++)
				if (n % p[i] == 0) {
					tmp = p[i];
					break;
				}
		}
		f[l] = 0;
		while (n % tmp == 0) {
			n /= tmp;
			f[l]++;
		}
		b[l++] = tmp;
	}
}

int main() {
	ll n, l;
	init();
	while (scanf("%lld", &n) != EOF && n) {
		cal(4*n-3, l, b, f);
		ll sum = 1;
		for (int i = 0; i < l; i++)
			sum *= f[i] + 1;
		printf("%lld %lld\n", n, sum);
	}
	return 0;
}