小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的状况下,仅凭这两种金币,有些物品他是没法准确支付的。如今小 凯想知道在没法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在 小凯没法准确支付的商品。spa
输入格式:it
两个正整数 aa 和 bb ,它们之间用一个空格隔开,表示小凯中金币的面值。io
输出格式:gc
一个正整数 NN ,表示不找零的状况下,小凯用手中的金币不能准确支付的最贵的物品的价值。im
输入样例#1: 复制支付
3 7
输出样例#1: 复制数据
11
【输入输出样例 1 说明】di
小凯手中有面值为 33 和 77 的金币无数个,在不找零的前提下没法准确支付价值为 1, 2,4,5,8,111,2,4,5,8,11 的物品,其中最贵的物品价值为 1111 ,比 1111 贵的物品都能买到,好比:time
12 = 3 \times 4 + 7 \times 012=3×4+7×0return
13 = 3 \times 2 + 7 \times 113=3×2+7×1
14 = 3 \times 0 + 7 \times 214=3×0+7×2
15 = 3 \times 5 + 7 \times 015=3×5+7×0
【数据范围与约定】
对于 30\%30% 的数据: 1 \le a,b \le 501≤a,b≤50 。
对于 60\%60% 的数据: 1 \le a,b \le 10^41≤a,b≤104 。
对于 100\%100% 的数据: 1 \le a,b \le 10^91≤a,b≤109 。
#include<stdio.h>
#include<algorithm>
using namespace std;
long long c;
void gcd(long long a,long long b)
{
if(!b)
{
c=a;
return;
}
gcd(b,a%b);
}
int main()
{
long long a,b;
scanf("%lld%lld",&a,&b);
if(a>b)
gcd(a,b);
else
gcd(b,a);
printf("%lld",a*b/c-a-b);
return 0;
}
~~要用long long
~~结论太难推了,但能猜出来