首先:
裴蜀定理:若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使
ax+by=d
成立。
关于裴蜀定理的重要推论:
a,b互质的充要条件是存在整数x,y使ax+by=1.
小分析:
如果 (p, q) == d > 1
即,p, q的最大公约数 大于1, 那么所有不是d的数都凑不出来。比如: 6 和 4
所以这个题一定是: (p, q) == 1
,一定存在 ap + bq == 1
(俩数互质)
然后可以打表找规律hh
数论结论:
如果 $a,b$ 均是正整数且互质,那么由 $ax+by,x≥0,y≥0 $不能凑出的最大数是 $ab−a−b$
代码~:
#include<iostream>
using namespace std;
int main()
{
int p, q;
cin >> p >> q;
cout << p * q - p - q << endl;
return 0;
}
愚蠢的我,在这道题里,学到的第一个并不是公式,而是如何去暴力打表找规律hh
打表找规律
- dfs:
ax + by == m
给定一个m,看是否能用p, q凑出来, 如果最后m == 0
, 就凑出来了~
bool dfs (int m, int a, int b)
{
if (!m) return true;
if (m >= a && dfs(m - a, a, b)) return true;
if (m >= b && dfs(m - b, a, b)) return true;
return false;
}
int main()
{
int a, b;
cin >> a >> b;
int res = 0;
for (int i = 1; i <= 10000; i ++ )
{
if(!dfs(i, a, b)) res = i;
}
cout << res << endl;
return 0;
}
- 也是
ax + by == 0
找最大的凑不出来的数
int main()
{
int a, b;
cin >> a >> b;
bool st[10000000];
for (int i = 0; i <= 1000; i ++ )
for (int j = 0; j <= 1000; j ++)
if (!st[i * a + j * b]) st[i * a + j * b] = true;
for (int i = 1000; ; i -- )
if (!st[i])
{
cout << i << endl;
break;
}
return 0;
}