Cod sursa(job #588545)

Utilizator crushackPopescu Silviu crushack Data 8 mai 2011 16:00:25
Problema NumMst Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <stdio.h>
#define NMax 10000000

typedef long long ll;
const char IN[]="nummst.in",OUT[]="nummst.out";

int N,Rez=-1,R1,R2;

int cmmdc(int a,int b)
{
	int r;
	while (b)
		b= (r=a%b,a=b,r);
	return a;
}

int main()
{
	int i,d;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	fclose(stdin);
	
	for (d=2;N%d;++d);
	for (i=1;i<=N;++i) if (cmmdc(i,N-i)==N/d && i*(ll)(N-i)/cmmdc(i,N-i)>Rez)
		Rez=i*(ll)(N-i)/cmmdc(i,N-i),R1=i,R2=N-i;
	
	freopen(OUT,"w",stdout);
	printf("%d %d\n",R1,R2);
	fclose(stdout);
	
	return 0;
}