[UVA][math] 10174 - Couple-Bachelor-Spinster Numbers.＠Morris' Blog

2013-05-04 14:32:45| 人氣907| 回應0 | 上一篇 | 下一篇

[UVA][math] 10174 - Couple-Bachelor-Spinster Numbers.

推薦 0 收藏 0 轉貼0 訂閱站台

Problem G

Couple-Bachelor-Spinster Numbers

Input: standard input

Output: standard output

Time Limit: 2 seconds

Can any number be expressed as a subtraction of two squares? The numbers, which can be expressed in such a way, are called square-couple numbers. Your job is to find out

a) If a number is square couple number.

b) If the number is square couple then find that format.

c) Find out how many square couple numbers are there within a certain range (including the terminal numbers).

Input

Each set of input is given in a single line. Each input set may contain one or two signed 32 bit integer numbers. Input is terminated by end of file.

Output

If there is only a single number N in a single line then print two non-negative integer numbers a and b, such that a*a-b*b = N. If the number cannot be expressed in such a format then print the line “Bachelor Number.” in a single line if such number is even and print the line “Spinster Number.” if the number is odd.

If there are two numbers n1 and n2 in the input then print how many bachelor numbers are within n1 and n2 (including n1 and n2). Note that (n1≤n2 and (n2- n1)<=1000000).

Sample Input:

6
12
3

Sample Output:

Bachelor Number.
4 2
2 1

Shahriar Manzoor

“If all the sides of a cube were identical, how could we tell which side is face up?”

這題要稍做觀察, 得到 Bachelor Number = 2, 6, 10, 14, 18, ....

正負是相同的, 因此在詢問區間的時候, 可以 O(1),
區間計算也要稍為判斷一下, 如果跨越正負的話, 是要做相加的。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
int check(long long n, int flag) {
    if(n == 0) {
        printf("0 0\n");
        return 1;
    }
    int neg = 0;
    long long i, sq;
    long long a, b, c, d;
    if(n < 0)   neg = 1, n = -n;
    sq = (long long)sqrt(n);
    for(i = sq; i >= 1; i--) {
        if(n%i == 0) {
            c = i; //a-b
            d = n/i;//a+b
            if((c+d)%2 == 0 && (c-d)%2 == 0) {
                a = (c+d)/2;
                b = (d-c)/2;
                if(a >= 0 && b >= 0) {
                    if(flag) {
                        if(neg)
                            printf("%lld %lld\n", b, a);
                        else
                            printf("%lld %lld\n", a, b);
                    }
                    return 1;
                }
            }
        }
    }
    if(flag) {
        if(n%2)
            puts("Spinster Number.");
        else
            puts("Bachelor Number.");
    }
    return 0;
}
int cntBachelor(long long n1) {
    if(n1 < 0) n1 = -n1;
    if(n1 < 2) return 0;
    return (n1-2)/4+1;
}
int main() {
    char cmd[50];
    long long n1, n2;
    while(gets(cmd)) {
        if(sscanf(cmd,"%lld %lld", &n1, &n2) == 2) {
            long long i, j, t1, t2;
            if(n1 > n2) swap(n1, n2);
            if(n1 < 0 && n2 > 0) {
                t1 = cntBachelor(n1);
                t2 = cntBachelor(n2);
                j = t1+t2;
            } else {
                if(n1 < 0) n1 = -n1, n2 = -n2;
                t1 = cntBachelor(abs(n1)-1);
                t2 = cntBachelor(n2);
                j = t2-t1;
            }
            printf("%lld\n", j);
        } else {
            sscanf(cmd, "%lld", &n1);
            check(n1, 1);
        }
    }
    return 0;
}

我要檢舉

#10174#Couple-Bachelor#Spinster Numbers#數學

台長： Morris

您可能對以下文章有興趣

c112. Optimal Array Multiplication Sequence

[UVA][Java] 10494 - If We Were a Child Again

[UVA][dp] 1096 - The Islands

[UVA][maxflow] 12159 - Gun Fight

人氣(907) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][math] 10990 - Another New Function
此分類上一篇:[UVA][dp] 10039 - Railroads

回應(0)