洛谷P3951 小凯的疑惑

题目:https://www.luogu.org/problemnew/show/3951

题目描述

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在 小凯无法准确支付的商品。

输入输出格式

输入格式:

输入数据仅一行,包含两个正整数 aa 和 bb,它们之间用一个空格隔开,表示小凯手 中金币的面值。

输出格式:

输出文件仅一行,一个正整数 NN,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。

输入输出样例

输入样例#1: 
3 7
输出样例#1: 
11

说明

【输入输出样例 1 说明】

小凯手中有面值为3和7的金币无数个,在不找零的前提下无法准确支付价值为1、 2、4、5、8、11 的物品,其中最贵的物品价值为 11,比 11 贵的物品都能买到,比如:

12=3×4+7×0

13=3×2+7×1

14=3×0+7×2

15=3×5+7×0

【数据范围与约定】

对于 30%的数据:1a,b50。

对于 60%的数据:1a,b10^4。

对于 100%的数据:1a,b10^9。

解析

让人又爱又恨的一道题目。orz

话说这道题在考场上推了半小时的exgcd。。。

但是就是推不出来。

于是lz恼了,开始打表找规律,

结果惊奇地发现答案怎么都是a*b-a-b啊?。。。。。。。

然后我就英勇地抱着九死一生的心态敲上去了。。。。。。。

结果竟然是正解orz。

好吧,这道题:

歪解:打表不解释。整几个数看看就行。

正解:乱搞啊orz。

(在jhy大佬的帮助下已更新,顺便再次%%%jhy大佬)

(在同余上乱搞)

假设a,b为3和5吧。

那么,5,10,15,......都能取到。

3+5,3+10,3+15......都能取到。

%5意义下,同余系取到的顺序依次为

0,3 此时为5*0+x

1,4 此时为5*1+x

2    此时为5*2+x

往后的都不用看了吧。。。。。。显然都能取到了。

最后取到的同余系便是a*(b-1)%b=2。此时取到的数是a*(b-1)=12。

再往后不用看了,都取到了。

然后再想一想,这次取到a*(b-1),又要保证%3同余系的最后一个。

那么,用上面相同的思想,寻找a的同余系。

a的同余系找到a*(b-1)就行了,因为后面的已经被取到了。

从上面的方法上可以看出,剩余一个是没有覆盖的。即取不到(请自己思考)

我们可以发现,如果同余系从0开始,变化了一个周期又变成0,那么最后取到的便是第二个周期开始的0取到的数减去你加的数(请仔细体会一下这句话)

所以同余没覆盖到的数-b即可,即a*(b-1)-b=a*b-a-b

我这么说,有几个人能听懂呢orz。

在此%%%jhy大佬,10min推出来orz。蒟蒻我想了半天。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define ll long long
 8 ll a,b,ans;
 9 int main(){
10     //freopen("math.in","r",stdin);
11     //freopen("math.out","w",stdout);
12     cin>>a>>b;
13     ans=a*b-(a+b);
14     cout<<ans;
15     //fclose(stdin);
16     //fclose(stdout);
17     return 0;
18 }
View Code
原文地址:https://www.cnblogs.com/gjc1124646822/p/7841575.html