Codeforces #275 div2_html/css_WEB-ITnose

Link: codeforce #275 div2

A.Counterexample

Question: Given the left and right intervals [l, r], find the three numbers a, b in the interval ,c makes a and b mutually prime,

b and c are mutually prime, but a and c are not mutually prime. If they do not exist, output -1

Analysis: Find continuous even-odd sequences Just

#include<stdio.h>int main(){    __int64 l,r;    scanf("%I64d%I64d",&l,&r);    if(l%2)        l++;    if(r-l<2)        printf("-1\n");    else    printf("%I64d %I64d %I64d",l,l+1,l+2);    return 0;}

B.Friends and Presents

Question: Construct two sequences, the first sequence is There are cnt1 numbers and there cannot be multiples of x.

The second sequence must have cnt2 numbers and there cannot be multiples of y. Two sequences cannot have the same number.

is required to find the minimum value of the maximum number in the two sequences.

Analysis: m=num - num / x, is the number of numbers from 1 to num that does not contain multiples of x

n=num - num / y, is the number from 1 to num that does not The number of numbers containing multiples of ;=cnt2

Because two sequences cannot have the same number, so cnt1 cnt2 <= num - num / (x * y)

Then binary search for the minimum value of num

#include<stdio.h>int main(){    __int64 x,y,cnt1,cnt2,m,n;    __int64 l,r,mid;    scanf("%I64d%I64d%I64d%I64d",&cnt1,&cnt2,&x,&y);    l=1;    r=1e12;    while(l<r){        mid=(l+r)/2;        m=mid-mid/x;        n=mid-mid/y;        if(m>=cnt1&&n>=cnt2&&mid-mid/(x*y)>=cnt1+cnt2)            r=mid;        else            l=mid+1;    }    printf("%I64d\n",r);    return 0;}

C.Diverse Permutation

Question: Find a sequence containing n numbers from 1-n, The number of different absolute values ​​of the difference between two adjacent elements is required to be k

Analysis: There are n-1 differences in n numbers, and it is necessary to ensure that the absolute values ​​of the k differences are different,

Then there are n-k-1 differences with the same difference. You can first output the n-k numbers between [1, n-k] in order,

and then output the minimum and maximum values ​​of the remaining numbers in sequence until you lose Until n numbers are reached.

#include<stdio.h>int main(){    int n,k,i,j,num;    scanf("%d%d",&n,&k);    num=n-k-1;    for(i=1;i<=num;i++)        printf("%d ",i);    j=n;    while(num<n){        printf("%d",i++);        if(num!=n)            printf(" ");        num++;        if(num==n)            break;        printf("%d",j--);        if(num!=n)            printf(" ");        num++;    }    return 0;}