1430. Crime and Punishment(枚举)

时间:2022-09-03 13:50:25

1430

即使是枚举 也是有一定技术含量的 对于ax+by = n; 枚举max(a,b)中的系数 这样可以确定另一个 但问题是如何确定上限 假设max(a,b) = a,很显然是不会超n/a的 但这样还是会超时的

可以设想一下假如x比b大 那么它可以拆分为x'+b吧 那把b合并y那里就好了 很明显也是不会超过b的 这样复杂度就不会超过sqrt(n)

1430. Crime and Punishment(枚举)1430. Crime and Punishment(枚举)
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<cmath>
 7 using namespace std;
 8 #define LL long long
 9 int main()
10 {
11     LL a,b,n,i;
12     while(cin>>a>>b>>n)
13     {
14         int aa = a,bb = b;
15         if(n%a==0)
16         cout<<n/a<<" "<<"0\n";
17         else if(n%b==0)
18         cout<<"0 "<<n/b<<endl;
19         else if(a==b)
20         {
21             printf("%lld %d\n",n/a,0);
22         }
23         else
24         {
25             LL t;
26             if(a<b){t = a;a = b;b = t;}
27             int minz = n+1,x,y;
28             for(i = 0 ; i <= min(n/a,b) ; i++)
29             {
30                 int o = (n-a*i)%b;
31                 if(o<minz)
32                 {
33                     minz = o;
34                     x = i;
35                     y = (n-a*i)/b;
36                 }
37                 if(o==0) break;
38             }
39             if(aa>bb)
40             cout<<x<<" "<<y<<endl;
41             else
42             cout<<y<<" "<<x<<endl;
43         }
44     }
45     return 0;
46 }
View Code