Cod sursa(job #586099)

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

long long n;

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

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

long long cmmdc(long long a, long 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 long d=3; d<=n; d++)
				if(n%d==0)
				{
					long long c = n/d;
					//long a, aa, b, bb, cma, cmb, sh1, sh2;
					long long a, b, cm, cmmmc=0, sh1, sh2;
					for(long long j=1; j<=d; j++)
					{
						a = j*c; b = (d-j)*c;
						cm = (a*b)/cmmdc(a, b);
						if(cm < cmmmc)
							cmmmc = cm, sh1 = a, sh2 = b;
					}
					long long aux;
					if(sh1 > sh2)
					{
						aux = sh1;
						sh1 = sh2;
						sh2 = aux;
					}
					printf("%lld %lld", sh1, sh2);
					break;
				}
		}
	}
	else
		printf("%lld %lld", n/2, n/2);

}

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