リンク: codeforce #275 div2
A.反例
質問: 左右の区間 [l, r] が与えられた場合、a と b が互いに素であるような区間内の 3 つの数値 a、b、c を見つけます。
b c と互いに素ですが、a と c が互いに素でない場合は、-1 を出力します
分析: 連続する偶奇数列を見つけるだけです
#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。友達とプレゼント
ヒント: 2 つのシーケンスを作成します。最初のシーケンスには cnt1 の数値が必要であり、x の倍数があってはなりません。
2 番目のシーケンスには cnt2 の数値が必要で、y の倍数があってはなりません。 2 つのシーケンスが同じ数値を持つことはできません。
では、2 つのシーケンス内の最大数値の最小値を見つける必要があります。
分析: m=num - num / x、x の倍数を含まない 1 から num までの数値の数
n=num - num / y、x の倍数を含まない 1 から num までの数値の数x の倍数を含む
num/(x*y) は、x の倍数でもあり y の倍数でもある数値です
つまり、m>=cnt1 および n>=cnt2
2 つのシーケンスが同じものを持つことはできないため数値なので、cnt1 + cnt2
次に、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
質問: を含む n を見つけます1-n 一連の数値の場合、隣接する 2 つの要素間の差の絶対値の異なる数が k である必要があります
分析: n 個の数値には n-1 個の違いがあり、次のことを確認する必要があります。 k 個の差の絶対値は異なります。
次に、同じ差を持つ n-k-1 個の差が存在します。まず、[1, n-k] の間の n-k 個の数値を順番に出力できます。
次に、最小値と最大値を出力します。
#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;}