AcWing 1360. 有序分数
原题链接
简单
作者:
缇拉鞠
,
2024-03-18 20:56:57
,
所有人可见
,
阅读 7
暴力大优先队列如何呢 $O(n^?)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double, pair<ll,ll> > pll;
#define x first
#define y second
void solve() {
priority_queue<pll,vector<pll>,greater<pll> > q;
ll n;
cin>>n;
for(ll i=1;i<=n;i++){
for(ll j=i+1;j<=n;j++){
if(__gcd(i,j)==1)q.push({(double)i/j,{i,j}});
}
}
cout<<"0/1"<<endl;
while(!q.empty()){
pll g=q.top();
q.pop();
cout<<g.y.x<<"/"<<g.y.y<<endl;
}
cout<<"1/1"<<endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}