NOIP 2017 小凯的疑惑
NOIP 2017 小凯的疑惑
# NOIP 2017 小凯的疑惑
思路
-
a,b互质 - 求最大不能表示出来的数k
- 则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内的所有数字都遍历了一遍。
设 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;
}
版权声明：本文为galaxy-yr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。