[UVA][math] 10174 - Couple-Bachelor-Spinster Numbers.
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:
612
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 <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;
}