島嶼渡假↘下殺$4900起直擊★美車模手癢不小心...吉隆坡最便宜行程一覽表破戒!比丘吃葷 連3次...
2012-12-21 16:16:16 人氣(250) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][因數個數] 12005 - Find Solutions

0
收藏
0
推薦


  Find Solutions 

Look at the following equation:

c = ab - $displaystyle {frac{{a+b}}{{2}}}$ + 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 < n$ le$1014). 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).


c-1 = a*b - (a+b)/2

(a-1/2)(-2b+1) = -2ab+b+a-1/2
(2*a+1)(2*b+1) = 4*c-3
求 a, b 的可行解,又 4*c-3 是奇數,因數個數畢定是答案。

#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;
}


12005Find Solutions
台長:Morris
人氣(250) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][dp] 12034 - Race
此分類上一篇:[UVA][cycle] 11036 - Eventually Periodic Sequence

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文