# NOIP 2017 小凯的疑惑

思路

  1. a,b 互质
  2. 求最大不能表示出来的数k
  3. 则k与 a,b 互质
这里有一个结论：（网上有证明）不过我是打表找的规律

若 x,y(设x<y) 互质 则 :
\(nx\equiv\)a (mod y)若将x依次加倍则可以得
nx mod y|ans
---|---|
x| a |
2x| 2a mod y
3x|3a mod y|
4x |4a mod y|
...|...|
yx|ya mod y|

这时a的值刚好把 0 ~ y-1内的所有数字都遍历了一遍。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

设 k>x*y ,如果我们要用x,y来拼出k

k=p*y+c(0<c<y && p>=x)

又 \(\because\) nx mod y =c 且n<p ,k=nx + (p-n)y
\(\therefore\) k一定可以被x,y拼出来

由此可知：我们要求的k一定<x*y
___
又\(\because\) x*y \(\equiv\)y (mod y)
x(y-1) \(\equiv\)y-x (mod y)
x(y-1)-(y-1) \(\equiv\) 1-x
(x-1)(y-1) \(\equiv\) 1-x
(x-1)(y-1)-1 \(\equiv\) -x
又\(\because\) x,y为正整数
\(\therefore\) -x<0 ,此时对于x,y>0无解
好吧，其实说来说去重点在这里
代码如下:

#include<iostream>
using namespace std;
int main()
{
    long long a,b;//a,b一定要开long long 
    cin>>a>>b;
    cout<<a*b-a-b<<endl;
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄