Cod sursa(job #585767)

Utilizator radubbRadu B radubb Data 30 aprilie 2011 11:44:22
Problema NumMst Scor 24
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.09 kb
#include <cstdio>
#include <cmath>
using namespace std;

long n;

void citire()
{
	freopen("nummst.in","r",stdin); scanf("%ld", &n);
}

bool prim(long x)
{
	for(long d=2; d<=sqrt(double(x)); d++)
		if(x%d==0)
			return 0;
	return 1;
}

long cmmdc(long a, long b)
{
    if((!a) || (!b)) return a+b;
    if(a>b) return cmmdc(a%b,b);
    return cmmdc(a,b%a);
}

void solve()
{
	if(n & 1)
	{
		if( prim(n) )
			printf("%ld %ld", n/2, n/2+1);
		else
		{
			for(long d=3; d<=n; d++)
				if(n%d==0)
				{
					long c = n/d;
					long a, aa, b, bb, cma, cmb, sh1, sh2;
					a = c*(d-1); aa = c;
					b = c*(d/2+1); bb = c*(d - d/2-1);
					cma = cmmdc(a, aa); cmb = cmmdc(b, bb);
					if(cma > cmb)
						sh1 = a, sh2 = aa;
					else if( cma < cmb)
						sh1 = b, sh2 = bb;
					else if( ( (a*aa)/cma ) > ( (b*bb)/cmb ) )
						sh1 = a, sh2 = aa;
					else
						sh1 = b, sh2 = bb;
					printf("%ld %ld", sh1, sh2);
					break;
				}
		}
	}
	else
		printf("%ld %ld", n/2, n/2);

}

int main()
{
	freopen("nummst.out","w",stdout);
	citire();
	solve();
	return 0;
}