我的代码看起来复杂度是n^2*logn【枚举i,j==n^2 ， 判断gcd==logn】 （n=1e5）但为什么过了呢？
因为数据里限定了m也是1e5级别的数
如果impossible 【及贪心完造的边还没有m这么多】，那n一定很小，小到n^2 * logn可以过；
如果possible，那一定n^2还没有枚举完就造完m条边，直接break了。【因为n^2枚举完造的边与m不是一个数量级的数】
1 #include<iostream> 2 using namespace std; 3 4 int u[100005],v[100005],pool; 5 6 int gcd(int a,int b){//a大于b 7 if(b==0) return a; 8 return gcd(b,a%b); 9 } 10 //connected 11 int main(){ 12 int n,m; cin>>n>>m; 13 14 if(m<n-1) { cout<<"Impossible"; return 0; } 15 16 for(int i=1;i<=n;i++){//u向v建边不会影响其余的边，因为只和gcd有关 17 for(int j=i+1;j<=n;j++){ 18 if(pool==m) break; 19 if( gcd(j,i)==1 ) { u[++pool]=i; v[pool]=j; } 20 } 21 if(pool==m) break; 22 } 23 24 if(pool==m){ 25 cout<<"Possible"<<endl; 26 for(int i=1;i<=pool;i++) cout<<u[i]<<" "<<v[i]<<endl; 27 } 28 else cout<<"Impossible"; 29 30 return 0; 31 }
Codeforces 1009D Relatively Prime Graph 【贪心】【复杂度分析】
原文：https://www.cnblogs.com/ZhenghangHu/p/9313362.html