P3951 小凯的疑惑

题解

题意也就是求解不能用 ax+by 表示的最大数 ans（a,b,x,y,都是正整数）

P3951 小凯的疑惑

给定 a ( =7 ) , b ( =3 )

我们可以把数轴非负半轴上的数按照a的剩余类分成a列，如上图

所以 a 的倍数一定可以取到，此时 y=0，那么我们把 a 的倍数这一列划掉

然后我们再考虑 y!=0的情况：

（1）b的倍数一定可以取到，此时 x=0

（2）和b %a 同余的数字一定可以取到，其实就是确定了 y，then确定了by，加上 a 的倍数

所以我们就可以把 b 的倍数以及和它%a同余的数字划掉，表现在图中，也就是：

把b的倍数那一列划掉

最后总会出现 a 和 b 把数轴上的点（除了仅有的几个点）全部覆盖

问题也就是求这仅有的几个点中最大的那一个

当我们把数轴上的数字分成 a 列时，自然会有一列被 a 划掉

还剩下a-1列要被 b 及其倍数划掉

b每扩大一倍，就会覆盖掉一列（因为大前提保证 gcd(a,b)=1 ）

那么当 b 扩大到第a-1倍时，就把剩下的所有数字覆盖了

但是 b*(a-1) 这一列中，b*(a-1)上面的那个数字是一定不会被覆盖的，与它同一行的所有数字都会被覆盖掉，所以这个数字就是要求的最大值

ans = b * ( a-1 ) - a

= a * b - a - b

代码

#include<bits/stdc++.h>

using namespace std;

long long a,b;

int main()

{

    scanf("%d%d",&a,&b);

    printf("%ld\n",a*b-a-b);

    return ;

}

秒客网