CF A fraction

A. Fraction

Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction CF A fraction is called proper iff its numerator is smaller than its denominator (a < b) and that the fraction is called irreducible if its numerator and its denominator are coprime (they do not have positive common divisors except 1).

During his free time, Petya thinks about proper irreducible fractions and converts them to decimals using the calculator. One day he mistakenly pressed addition button ( + ) instead of division button (÷) and got sum of numerator and denominator that was equal to ninstead of the expected decimal notation.

Petya wanted to restore the original fraction, but soon he realized that it might not be done uniquely. That's why he decided to determine maximum possible proper irreducible fraction CF A fraction such that sum of its numerator and denominator equals n. Help Petya deal with this problem.

Input

In the only line of input there is an integer n (3 ≤ n ≤ 1000), the sum of numerator and denominator of the fraction.

Output

Output two space-separated positive integers a and b, numerator and denominator of the maximum possible proper irreducible fraction satisfying the given sum.

Examples input Copy
3
output Copy
1 2
input Copy
4
output Copy
1 3
input Copy
12
output Copy
5 7

这道题就是给一个整数n,看看把它拆成分子i和分母n-i,找最大的分子分母互质的真分数

模拟即可

注意是从中间开始往两边,看看是不是gcd(a,b)==1就行了(互质)

一大堆英语读累死了,发现就是这么个...题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a,b;
 4 
 5 int gcd(int a,int b)
 6 {
 7       if(b==0)return a;
 8       
 9       return gcd(b,a%b);
10 }
11 int main(){
12       int n;cin>>n;
13       
14       if(n%2==0)a=n/2,b=n/2;
15       
16       else a=n/2,b=n/2+1;
17       
18       while(gcd(a,b)!=1)
19       {
20             a--;
21             b++;
22       }
23       cout<<a<<" "<<b;
24       return 0;
25       
26 }

数学题啊~还是~水题~还是~某个少女写了15分钟的~绝世好题~

而且,刚开始用的代码比这个麻烦,找揍

上一篇:【leetcode】657. Robot Return to Origin


下一篇:What is OWIN? A Beginners Guide