NOIP 2017小凯的疑惑

\(Description\)

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在 小凯无法准确支付的商品。

\(Input:a、b\ ,\ Output:ans\)

\(Solution\)

\(1.Exgcd\)

来自洛谷的题解，讲得很清楚

\(Code\)

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll t;
void exgcd(ll a,ll b,ll& x,ll& y){
    if(!b){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-a/b*y;
}

ll a,b,x,y,xx,yy;
int main(){
    scanf("%lld%lld",&a,&b);
    exgcd(a,b,x,y);
    t=x/b;
    x-=t*b;
    y+=t*a;
    for(;x<0;)x+=b,y-=a;
    xx=x;
    for(;x>0;)x-=b,y+=a;
    yy=y;
    printf("%lld\n",a*(xx-1)+b*(yy-1)-1);
    return 0;
}

\(O(1)结论\)

#include<cstdio>
#include<iostream>
#define re register
#define ll long long

using namespace std;

inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll a,b;
int main()
{
    a=read(),b=read();
    cout<<a*b-a-b;
    return 0;
}

反证法
这有一篇反证法的博客

总之，考试的时候还是打表找规律比推结论更好用。
当题目输入的数据\(<=2\)个时，可以尝试打表找规律，会有奇效