首页 > 代码库 > 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 }
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 }
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 }
将写得过程中的代码 全贴上来 给自己点 经验#24...
today:
用我一生 再换你十年天真无暇
用我一生 再陪你十年颠沛流离
hdu--5019--开始参加bc了
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。