即使是枚举 也是有一定技术含量的 对于ax+by = n； 枚举max(a,b)中的系数 这样可以确定另一个 但问题是如何确定上限 假设max(a,b) = a,很显然是不会超n/a的 但这样还是会超时的
可以设想一下假如x比b大 那么它可以拆分为x'+b吧 那把b合并y那里就好了 很明显也是不会超过b的 这样复杂度就不会超过sqrt(n)
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 "; 17 else if(n%b==0) 18 cout<<"0 "<<n/b<<endl; 19 else if(a==b) 20 { 21 printf("%lld %d ",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 }