首页 > 代码库 > hdu 5916

hdu 5916

题意:sigma(gcd(pi,pi+1)),输出一个和严格第k小的p序列

分析:相邻的两个数gcd为1,并且题目给出提示2*k<=n,gcd(k,2*k)=k,这只要保证剩下的相邻都是1,就可以保证这个序列是符合条件的

       如何来保证呢,2*k 和2*k+1 2*k -1必然两两gcd=1,问题在于怎么处理k-1 k+1之间的矛盾 ,那么我先利用第一个条件,把k后面的都放进去,然后放1-  k-1,1必然与任意数gcd为1

#include<bits/stdc++.h>using namespace std;int main(){    int t,n,cas=1,k;    cin>>t;    while(t--){        cin>>n>>k;        printf("Case #%d: %d %d",cas++,2*k,k);        for(int i=k+1;i<=n;i++){            if(i==2*k)continue;            printf(" %d",i);        }        for(int i=1;i<=k-1;i++)printf(" %d",i);        puts("");    }    return 0;}

 

hdu 5916