UVA - 12005 Find Solutions （最小因子分解）

Description

Find Solutions

Look at the following equation:

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
題意：求等式是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 
#include 
#include 
#include 
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;
}