首页 > 代码库 > hdu--5019--开始参加bc了

hdu--5019--开始参加bc了

开始 有时间 晚上bc比赛也去做了

这题 数据很大 虽然也注意到了 但还是一直tle

...

一开始用set做 tle

然后用vector做 tle

才发现是应该先去求出gcd(x,y)这样可以减少很多遍历

 1 #include <iostream> 2 #include <set> 3 #include <algorithm> 4 using namespace std; 5  6 typedef long long LL; 7 set<LL>s; 8  9 void solve( LL x , LL y )10 {11     for( LL i = 1 ; i<=y/i && i<=x ; i++ )12     {13         if( x%i ==0 && y%i ==0 )14         {15             s.insert(i);16         }17         if( x%(y/i)==0 )18         {19             s.insert(y/i);20         }21     }22 }23 24 int main()25 {26     cin.sync_with_stdio(false);27     int t , cnt;28     LL x , y , k , temp , size;29     cin >> t;30     while( t-- )31     {32         s.clear();33         cnt = 0;34         set<LL>::iterator it;35         cin >> x >> y >> k;36         if( x>y )37         {38             swap(x,y);39         }40         solve(x,y);41         size = s.size();42         if( size<k )43             cout << -1 << endl;44         for( it = s.begin() ; it!=s.end() ; it++ )45         {46             ++ cnt;47             if( cnt==size-k+1 )48                 cout << *it << endl;49         }50     }51     return 0;52 }
View Code
 1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 using namespace std; 5  6 typedef long long LL; 7 vector<LL> ve_left; 8 vector<LL> ve_right; 9 10 void solve( LL x , LL y )11 {12     for( LL i = 1 ; i<=y/i && i<=x ; i++ )13     {14         if( y%i == 0 )15         {16             if( x%i==0 )17             {18                 ve_left.push_back(i);19             }20             if( y/i<=x && x%(y/i)==0 && i!=y/i )21             {22                 ve_right.push_back(y/i);23             }24         }25     }26 27 }28 29 int main()30 {31     cin.sync_with_stdio(false);32     int t;33     LL x , y , k , Size , Size1 , Size2;34     cin >> t;35     while(t--)36     {37         ve_left.clear();38         ve_right.clear();39         cin >> x >> y >> k;40         if( x>y )41             swap( x , y );42         solve( x , y );43         Size1 = ve_left.size();44         Size2 = ve_right.size();45         Size = Size1 + Size2;46         if( Size<k )47             cout << -1 << endl;48         else49         {50             if( Size2>=k )51             {52                 cout << ve_right[k-1] <<endl;53             }54             else55             {56                 k -= Size2;57                 cout << ve_left[Size1-k] << endl;58             }59         }60     }61     return 0;62 }
View Code
 1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 using namespace std; 5  6 typedef long long LL; 7 vector<LL> ve; 8  9 LL gcd( LL x , LL y )10 {11     return y%x == 0 ? x : gcd( LL(y%x) , x );    12 }13 14 void solve( LL x , LL y , LL z )15 {16     for( LL i = 1 ; i<=z/i ; i++ )17     {18         if( z%i==0 )19         {20             ve.push_back(i);21             if( i!=z/i )22                 ve.push_back(z/i);        23         }24     }25 }26 27 int main()28 {29     cin.sync_with_stdio(false);30     int t;31     LL x , y , k , z , Size;32     cin >> t;33     while(t--)34     {35         ve.clear();36         cin >> x >> y >> k;37         if( x>y )38             swap( x , y );39         z = gcd(x,y);40         solve( x , y , z );41         Size = ve.size();42         if( Size<k )43             cout << -1 << endl;44         else45         {46             sort( ve.begin() , ve.end() );47             cout << ve[Size-k] << endl; 48         }49     }50     return 0;51 }
View Code

将写得过程中的代码 全贴上来 给自己点 经验#24...

 

today:

  用我一生 再换你十年天真无暇

  用我一生 再陪你十年颠沛流离

 

hdu--5019--开始参加bc了