DouKaku? 7637 こう。: 何も考えずに。(2^i * 3^j * 5^k なる整数)

Comment detail

何も考えずに。

#include <stdio.h>

int main(){
    int m=1;
    int n=0;
    int i,j,k;
    int v;
    
    do{
        v=m;
        i=0;
        j=0;
        k=0;
        while(v%2==0)v/=2,i++;
        while(v%3==0)v/=3,j++;
        while(v%5==0)v/=5,k++;
        if(v==1){
            printf("%d = 2^%d * 3^%d * 5^%d\n",m,i,j,k);
            n++;
        }
        m++;
    }while(n<100);
    return 0;
}

よく考えたら2で割るのにループはいりませんね。
i,j,kも省いてこんな感じかな。

#include <stdio.h>

int main(){
    int m,n,v;
    
    for(n=0,m=1;n<100;m++){
        v=m/(m&-m);
        while(v%3==0)v/=3;
        while(v%5==0)v/=5;
        if(v==1){
            printf("%d\n",m);
            n++;
        }
    }
    return 0;
}

（雑談です）
この v=m/(m&-m) というのは私には逆立ちしても思いつきそうにないんですが、有名なテクニックなんですか？
いまだになぜ上手くいくのかよくわかってないけど、ビットを書き出してみると確かにそうなるぽいですが・・・教えてえらいひと

m&-mの部分は一応知られたコードのはずです。
下位ビットから見て最初に1になるビットを検出するというコードとして知ったと思います。(この数字の意味は今回はじめて気づきましたが^^;;)

-mって言うのはmと足したとき0になる数字ですので、2進表記した場合の下位ビットから見て最初に1が出て来る場所まではmと同じ、それ以上は反転となる数字です。
-m=~m+1でもありますね。
4ビットでの例：
2=0010
-2=1110

3=0011
-3=1101

ここでm&-mをとれば、下から見て一番最初の1のみが残ることがわかります。
証明：
m=1*A+2*B+4*C+8*Dとすると
~m=1*~A+2*~B+4*~C+8*~D

-m=~m+1=1*A'+2*B'+4*C'+8*D'とすると
ビット加算はsum=a^b,Carry=a&bなので
A'=~A^1 = A
B'=~B^(~A&1) = ~B^~A =B^C
C'=~C^(~B&(~A&1)) =~C^(~B&~A)=C^(B|A)
D'=~D^(~C&(~B&(~A&1))) = ~D^(~C&~B&~A)=D^(C|B|A)

m&-m=1*A''+2*B''+4*C''+8*D''

a&(a^b)=a&(a&~b|~a&b)=a&~bより

A''=A&A'=A
B''=B&B'=B&(B^A) = B&~A
C''=C&C'=C&(C^(B|A)) = C&~(B|A) = C&~B&~A
D''=D&D'=D&(D^(C|B|A))=D&~(C|B|A)=D&~C&~B&~A

下位ビットがすべて0のときのみビットがたつことがわかる。
～～証明ここまで

さて、2で割るということは2進数で考えれば、右シフトです。2で割った余りというのはm&1となるわけなので、最下位ビットが0なら2の倍数です。
ここから考えれば最下位ビットから見て0の数だけ2で割れるわけです。

つまり先ほど求めたm&-mというのは、設問で言う2^iとなっていることがわかると思います。

というのでどうでしょう？

解説ありがとうございます。何をやっているかがようやく理解できました。
（式変形はこれからじっくり解読しようと思います。。）

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq