小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在 小凯无法准确支付的商品。
输入格式：
两个正整数 a 和 b，它们之间用一个空格隔开，表示小凯中金币的面值。
输出格式：
一个正整数 N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。
运用公式a*x+b*y=k，max(k)=a*b-a-b
1 //AC 2 //luoguP3951小凯的疑惑 3 #include<iostream> 4 using namespace std; 5 int main() 6 { 7 long long a,b; 8 cin>>a>>b; 9 cout<<a*b-a-b; 10 return 0; 11 }
简单粗暴的枚举，但是枚举量无疑是巨大的。每个枚举量的最大值都是a*b(根据上面推理的公式，且题目中给出a，b互质，说明结果一定会小于a*b)。逐一舍去可以被表示出来的数字（赋予1），最后再倒序从a*b-1开始输出第一个为零的数字
1 //60分 2 //luoguP3951小凯的疑惑 3 #include<iostream> 4 using namespace std; 5 bool number[1000000000]; 6 int main() 7 { 8 unsigned long long a,b; 9 cin>>a>>b; 10 for(unsigned long long i=0;i<a*b;i++) 11 for(unsigned long long j=0;j<a*b;j++) 12 { 13 if(i*a+j*b>a*b) break; 14 number[i*a+j*b]=1; 15 } 16 for(unsigned long long i=a*b-1;i>0;i--) 17 if(number[i]==0) {cout<<i;break;} 18 return 0; 19 }
之后，我下载了#13测试数据：66650775 6074462
对应的答案：404867527282813
你就知道为什么会不能通过了
因为对于每一个可以得到的商品的价格，再加上a或b，小凯也可以买到。那么每一个数字就有两种选择，直到数字超过了a*b
1 //30分 2 //luoguP3951小凯的疑惑 3 #include<iostream> 4 using namespace std; 5 unsigned long long a,b; 6 bool number[1000000000]; 7 void function(unsigned long long one){ 8 if(one>a*b) return; 9 number[one]=1; 10 //cout<<one<<endl;//倘若你输出每一次的one值，你就可以看到效率是多么的低。。。 11 function(one+a); 12 function(one+b); 13 } 14 int main() 15 { 16 cin>>a>>b; 17 function(0); 18 for(unsigned long long i=a*b-1;i>0;i--) 19 if(number[i]==0) {cout<<i;break;} 20 return 0; 21 }
总而言之，还是第一种方法好，但它也是最难理解的一种。
好吧，就这么草率的结束了吧！
原文：https://www.cnblogs.com/send-off-a-friend/p/10981339.html