Beta Round #61-D: Petya and His Friends

Codeforces

問題概要

n(<50)が与えられる。gcd(a[i],a[j])!=1, gcd(a[0],...,a[n-1])=1, a[i]!=a[j]を満たす数列(上界10^100)を出力する問題。

解法

n=2は解なしであることに注意。

  • すぐ思いつく解法：素数を小さい順にp[0],...,p[n-1]ととってくる。a[i]=(Πp[k])/p[i]とする。本番中は10^100を越えてしまうような気がして書かなかったけど、そんなことは無かった。
  • 賢い解法：a[0]=10, a[1]=15, a[2]=6, a[3]=12, a[4]=18, ...
  • 怪しげな解法：nを2進表記してどうたらこうたら。本番中にこんな解き方をしたせいで大分時間をとられた。どう考えても解法1で10^100を越えないかテストする方が速かった。
int ans[55];

int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

int main(){
    int i,N,m;
    __builtin_scanf("%d",&N);
    if(N==2){
        __builtin_printf("-1");
        return 0;
    }
    m = (1<<(32-__builtin_clz(N-1)))-1;
    for(i=0;i<N;i++) ans[i] = 1;
    for(i=0;i<N;i++) ans[i] *= ((i>>0)&1)?2:3;
    if(N>(1<<1))for(i=0;i<N;i++) ans[i] *= ((i>>1)&1)?3:5;
    if(N>(1<<2))for(i=0;i<N;i++) ans[i] *= ((i>>2)&1)?5:7;
    if(N>(1<<3))for(i=0;i<N;i++) ans[i] *= ((i>>3)&1)?7:11;
    if(N>(1<<4))for(i=0;i<N;i++) ans[i] *= ((i>>4)&1)?11:13;
    if(N>(1<<5))for(i=0;i<N;i++) ans[i] *= ((i>>5)&1)?13:17;
    for(i=0;i<N;i++)if((i&1) && (m&(~i)) < N && gcd(ans[i] ,ans[m&(~i)])==1){
        ans[m&(~i)] *= 19; ans[i] *= 19; 
    }
    for(i=0;i<N;i++) __builtin_printf("%d\n",ans[i]);
    return 0;
}