PKU演習問メモ(4/30)

No. Title 分類・解法 主観的難易度
1906 Three powers 多倍長整数演算 ★★☆☆☆

以下問題解説など

1906 Three powers

問題概要

3^n乗からなる集合S={1,3,9,27,...}がある。
このSの部分集合を小さいほうから{ },{1},{3},{1,3},[9},...と並べたときにn番目に来るような集合を求めよ。
nは19桁以下の整数とする。

解法

nが巨大なので多倍長計算が必要。n番目に来る部分集合には、
n-1を二進数で表したときにi桁目が1である⇔3^(i-1)が集合に含まれる
というような関係が成り立つ。よってこれをビットシフトなどで表現してやればよい。

ソースコード
	class pku1906{
		void run(){
			BigInteger[] pw=new BigInteger[300];
			pw[0]=BigInteger.ONE;
			for(int i=1;i<300;i++)pw[i]=pw[i-1].multiply(BigInteger.valueOf(3));
			
			Scanner sc=new Scanner(System.in);
			
			for(;;){
				BigInteger n=sc.nextBigInteger();
				if(n.equals(BigInteger.ZERO))break;
				if(n.equals(BigInteger.ONE)){
					System.out.println("{ }"); continue;
				}
				n=n.subtract(BigInteger.ONE);
				
				System.out.print("{ ");
				boolean f=true;
				for(int i=0;i<300;i++){
					
					if(n.and(BigInteger.ONE.shiftLeft(i)).equals(BigInteger.ZERO))continue;
					if(!f)System.out.print(", ");
					else f=false;
					
					System.out.print(pw[i]);
				}
				System.out.println(" }");
			}
		}
	}

(mainなどは略)
JavaC++に比べて横に長くなるなあ。