[蓝桥杯]买不到的数目
-
-
梁老师 北京小升初老师～
0 人点赞了该文章 · 75 浏览
4 7输出样例
17#include <iostream>using namespace std;bool dfs(int i, int n, int m){if (!i)return true;if (i >= n && dfs(i - n, n, m))return true;if (i >= m && dfs(i - m, n, m))return true;return false;}int main(){int n, m, res;scanf("%d %d", &n, &m);for (int i = 1; i < 1000; i++)if (!dfs(i, n, m))res = i;printf("%d", res);return 0;}
通过打了多组表，就发现了其具有的一些独特的规律
| m | n | d |
| 3 | 2 | 1 |
| 3 | 4 | 5 |
| 3 | 5 | 7 |
| 3 | 7 | 11 |
| 3 | 8 | 13 |
| 3 | 10 | 17 |
相邻组之间n每递增1，d对应的数也加1
很容易发现他是具有一种线性关系的即是(m-1)*n - m
利用输出样例，很好可以验证我们猜想，这样我们就得到了对应的答案。
最后放上代码
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;int main(){int n, m;scanf("%d %d", &n, &m);printf("%d", n * m - n - m);return 0;}
题后反思
解决问题后我咨询了一位来自北京交大的大佬@锦筝叹和一位来自华师大的大佬@lzw，按照他们的思路，我们将问题转化为一个线性表达式
即是d = ay+bx
a,b要是互质的正整数，x和y要是两个自然数，如果这个数d’不能被表出，则必然d'在表示的时候x或者y必有一个为负，故我们不妨设一个数n = a-b
这样就会有了以下的证明手稿
感谢来自华师大@lzw的相关推导证明
最后我们也就得到了这个题的结论，即两个互质的自然数，所不能表出的最大自然数为 a*b-a-b
添加 家长论坛微信
全部 0条评论