PKU演習問メモ(4/14) - simezi

No.	Title	分類・解法	主観的難易度
3604	Professor Ben	整数問題	★★★☆☆
2273	An Excel-lent Problem	実装問題・数学	★★☆☆☆
3112	Pie	二分法	★★☆☆☆

以下解説など。

3604 Professor Ben

問題概要

自然数nに対して、以下の値を求めよ。
Σ(iの約数の個数)^3, for ∀i∈{nの約数}

ただし与えられるnの個数は50万個以下、nは500万以下である。
例：6
6の約数は1,2,3,6

1の約数の個数の3乗は1^3,
2の約数の個数の3乗は2^3,
3の約数の個数の3乗は2^3,
6の約数の個数の3乗は4^3,

となり求める数は1+8+8+64=81

解法

nを素因数分解してn=p1^q1 p2^q2 p3^q3 ...
と表せたとすると、nの約数を全て生成するには
0≦a1≦q1,0≦a2≦q2, ...となるような自然数a1,a2, ...を全て選べば良い。

これには再帰を使うのが自然であるが、
ここでm=r1^s1 r2^s2 ...と素因数分解されるようなある数mの約数の個数は
(1+s1)(1+s2)...個であることに注意する。
すると約数を生成すると同時に(1+a1)(1+a2)...の積を計算しておけば、
約数の約数の個数（typoじゃないよ）も同時に計算できることがわかる。

よってこれを全て足してやれば求める数となる。
以下のコードでは素因数分解の高速化のために1から500万以下の全ての整数について、あらかじめその「最初の素因数」をエラトステネスの篩の応用で求めておいてみた。また、出現する可能性のある3乗の計算もあらかじめ行っておいた。
（多分テストケースが50万個なので効果はあるはず）

ソースコード

const int MX=5000001;
int ffct[MX],T[1200];

int factor[20],nf;
int rec(int c,int s)
{
	if(c==nf)return T[s];
	int ret=0;
	rep(i,factor[c])ret+=rec(c+1,s*(i+1));
	return ret;
}
int solve(int n)
{
	nf=0;
	while(n>1)
	{
		int c=0,f=ffct[n];
		while(ffct[n]==f)n/=f,c++;
		factor[nf++]=c+1;
	}
	return rec(0,1);
}

int main()
{
	ffct[1]=1;
	for(int i=2;i*i<MX;i++)if(!ffct[i])
	{
		ffct[i]=i;
		for(int j=i+i;j<MX;j+=i)if(!ffct[j])ffct[j]=i;
	}
	for(int i=(int)sqrt(MX);i<MX;i++)if(!ffct[i])ffct[i]=i;
	rep(i,1200)T[i]=i*i*i;
	
	int q,n; scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&n);
		printf("%d\n",solve(n));
	}
	
	return 0;
}

2273 An Excel-lent Problem

問題概要

表計算ソフトにおいて"R3C1"のようなR+行番号C+列番号の形で与えられたセルの座標を、エクセルで使われる座標系に変換せよ。
エクセルの座標系は"A3"のような列を表す文字列+行番号の形式である。
列番号はA,B,C,...,Zと続き、Z列の次の列はAAである。更にAA,AB,...AZ,BA,BB,...,ZZと続き、ZZ列の次の列はAAAであり、以下も同様とする。

解法

行番号は変換する必要がないので列について考える。
まずは列を表す文字が何文字になるかについて考察する。
1文字で表すことの出来る列は26列、2文字では26^2列...であるので、
Σ26^iがその次で列番号を超えるようなnが、文字数である。

行番号からΣ26^iの差をとれば、n桁のAAA...Aの並びから求める文字列が何番目にあるかがわかるが、これはAを0とみた26進数の変換に等しい。

以上の考察を実装する。

ソースコード

int main()
{
	string str;
	while(1)
	{
		cin>>str; fr(i,str)if(*i=='R'||*i=='C')*i=' ';
		stringstream ss(str);
		int a,b; ss>>a>>b;
		if(a==0&&b==0)break;
		
		b--;
		int len=1;
		for(int t=26;b>=t;t*=26)b-=t,len++;
		
		char ans[30]={0}; rep(i,len)ans[i]='A';
		for(int i=0;b;b/=26,i++)ans[i]+=b%26;
		reverse(ans,ans+len);
		
		cout<<ans<<a<<endl;
	}
	return 0;
}

3112 Pie

問題概要

半径r[i],高さ1のn個の円柱形をしたパイをf人の友達と自分に同じ大きさずつ分ける。
ただし、パイ片は一人二つ以上になってはならず、そのために無駄になるパイが出てもよい。
このとき一人分として取りうる最大のパイの量を求めよ。

解法

大きさaのパイ片をがいくつ取れるかは各パイの体積をaで割った商（小数点未満切り捨て）を足すことで求められる。
aを二分法により変化させながらf+1個のパイ片を取れる最大のaを求めればよい。

ただし誤差が結構厳しいので注意。

ソースコード

int n,f,sz[10000];

int getp(double a)
{
	int r=0;
	rep(i,n)
		r+=int(sz[i]/a);
	
	return r;
}

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		cin>>n>>f; double s=0;
		rep(i,n)cin>>sz[i],sz[i]*=sz[i],s+=sz[i];
		
		double lo=0,hi=s/f,mid;
		while(hi-lo>0.000001)
		{
			mid=(lo+hi)/2;
			if(getp(mid)>=f+1)lo=mid;
			else hi=mid;
		}
		printf("%.4f\n",mid*3.141592653589793);
	}
	return 0;
}