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(" }"); } } }