[UVa] 10174 - Couple-Bachelor-Spinster Numbers.

題目網址: http://goo.gl/Y6aLXQ

題意:
(from luckycat)


解法: 假設 N = x^2 - y^2 = (x+y) * (x-y) = a * b，推倒發現 x = (a+b)/2, y = (a-b)/2，我們就知道若N能夠分成 a, b 兩數相乘，且 a +/- b都是偶數，表示 a, b 必須是偶偶或奇奇，接著我們發現，若 N 是奇數，則 N 一定能夠等於 N * 1，代表 N 為奇數時必定能夠拆解成 x^2 - y^2，而 N 是偶數的情況，必要分成 偶 * 偶 ，則 N 就必須能夠被 4 整除，若 N 無法被 4 整除，則代表 N 無法是 x^2 - y^2。

TAG: Math

注意:

程式碼:

	/**
	* Tittle: 10174 - Couple-Bachelor-Spinster Numbers.
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/16
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	typedef long long ll;
	// declarations
	char buf[1000];
	// functions
	// main function
	int main( void )
	{
	ll a, b;
	ll x, y;
	int cnt;
	// input
	while( gets(buf) ) {
	if( sscanf( buf, "%lld%lld", &a, &b )==2 ) {
	if( (a&1LL) ) ++a;
	cnt = 0;
	for( ll i=a; i<=b; i+=2 ) {
	if( (i%4LL) ) ++cnt;
	}
	printf( "%d\n", cnt );
	} else {
	if( (a&1LL) || (a%4LL)==0 ) {
	b = a;
	if( a < 0LL ) a = -a;
	if( (a&1LL) ) x = (a+1LL)/2LL, y=(a-1LL)/2LL;
	else x = (a/4LL)+1LL, y = (a/4LL)-1LL;
	if( b < 0LL ) swap(x,y);
	printf( "%lld %lld\n", x, y );
	} else puts("Bachelor Number.");
	}
	}
	return 0;
	}

view raw 10174 - Couple-Bachelor-Spinster Numbers.cpp hosted with ❤ by GitHub