因子理论

因子理论"/>

因子理论

再次感叹自己的数学很悲剧。。。。转载地址.html

x 、y、n都是正整数，并且 显然，x >= n ， y >= n ，现在假设 y = n +k (k为正整数) ，那么带入公式，可以得出 x = (n*(n+k))/k = n*n/k + n; 由于x 是正整数，现在的关键问题就是要求出 n*n/ k 有多少组正整数的可能，显然，所要求的就是 n*n 因子的个数// 问题已经非常接近答案了，但是最后还有一个问题，n<= 10^9 ， 那么n*n <= 10^18 ,对于一个这么大的数字怎样才能求出它因子的个数呢？

命题1： 一个正整数 n 可以用素因子唯一表示为 p1^r1 * p2^r2 * ... pk^rk (其中 pi 为素数) , 那么这个数的因子的个数就是，(r1+1)*(r2+1)*...*(rk+1).

如果一个数字 n = p1^r1 * p2^r2 * ... pk^rk ，那么 n*n = p1^r1 * p2^r2 * ... pk^rk * p1^r1 * p2^r2 * ... pk^rk ，它的因子的个数就是 (2*r1+1)*(2*r2+1)*...*(2*rk+1).

这个问题就转化成了求 n <= 10^9 的素因子的问题，只需要先筛选出 sqrt(10^9) 内的素数，然后用n去试除 sqrt(n) 中的每一个即可，当然，n可能会有大于sqrt(n) 的因子呶//. 只试到 sqrt(n)，怎么找出所有的素因子呢，不妨想一想，如果n有大于sqrt(n) 的素因子，它会有几个，又是多少呢？ //.呵呵，很聪明的吧，先小自恋一下

#include <iostream>
#include <cmath>
using namespace std;
 
const int maxn = 50000;
int prime[10000] = { 2, 3, 5 };
int len;
 
int solve(int n ) {
    int i, j, ans, r, m, s;
    m = n;
    ans = 1;
    s = sqrt( (double)n );
    for( i=0; i<len; ++i ) {
        if( prime[i] > s+1 ) break;
        if( n % prime[i] == 0 ) {
            r = 0;
            while( m % prime[i] == 0 ) ++r, m/=prime[i];
            ans *= (2*r + 1);
        }
    }
    if( m > 1 ) ans *= 3;
    return (ans+1)/2;
}
 
void creatPrime() {
    int i, j, dis = 2;
    bool flag;
    len = 3;
    for( i=7; i<maxn; i+=dis ) {
        dis = 6 - dis;
        flag = true;
        for( j=0; prime[j]*prime[j]<=i; ++j ) {
            if( i % prime[j] == 0 ) {
                flag = false;
                break;
            }
        }
        if( flag ) prime[len++] = i;
    }
}
 
 
int main() {
//  freopen( "c:/aaa.txt", "r", stdin );
    int T, ca, n;
    creatPrime();
    scanf("%d", &T );
    for( ca=1; ca<=T; ++ca ) {
        printf("Scenario #%d:\n", ca );
        scanf("%d", &n );
        printf("%d\n\n", solve(n) );
    }
    return 0;
}