競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 107 - The Cat in the Hat

今回からfor文のマクロを一新してみましたが結局repを使っております。
慣れたものを使うほうがやはり早いのでしょうかね

- 問題概要

猫のお話です。
ある身長の猫がいます。その猫は自分が働く代わりに身長が自身の\frac{1}{N+1}の猫をN匹働かせることができます。
同様にそれぞれの猫も身長が自身の\frac{1}{N+1}の猫をN匹働かせることができます。
しかし、身長が1の猫はそれ以上小さい猫が存在しないため自分で働くしかありません。
最も大きい一匹の猫の身長と、実際に働いている身長が1の猫の数が与えられます。
働いていない猫の総数と全ての猫の身長の合計を出力してください。

- 解法

入力で与えられる二つの整数は、必ず次の形をしています。
(N)^m,(N-1)^m(N>=2,m>=0)
これは,最も大きい猫の身長をhとすると,ある猫の身長は\frac{h}{N^k}となることに由来します。
また、働いていない猫の総数は\sum_{i=0}^{m-1} (N-1)^i,
全ての猫の総数は\sum_{i=0}^{m} (N-1)^i*N^{m-i}となるため、
N,mがわかればO(n)で計算できます。
入力で与えられる整数nの規定がないので、1 \le n \le 10^9としましょう。
32bit整数の範囲内なのであり得ると思います。
m \ge 2の状態について尺取り法を使います。入力をX,Yとすると
初期値をN=2,m= (2^m \le Y)を満たす最大のmとすると、
(N^m > X)m--
(N^m < X)N++
(N^m == X) and ((N-1)^m == Y)終了
(N^m == X) and ((N-1)^m != Y)m--
これをm \ge 2を満たす限り行います。
N,mが決定せずm=1になったときはN=Xが確定しますのでm \ge 2のときだけループを回せばよいのです。
するとNの値は最大\sqrt{X},m乗の計算に\log mとなりますので、
とすると、計算量はO(\sqrt{X} \log (\log X) )となります。


- ソースコード

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>

using namespace std;

#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) for(auto (i)=(0);(i)<=(b);(i)++)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) for(auto (i)=(0);(i)<(b);(i)++)
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define LL long long
#include<fstream>
#include<ctime>


LL x, y;
LL n, m,l,cnt,ht;
LL tmp[40];
vector<pair<LL, LL> >cats;

inline LL power(LL num, LL p){
	LL t = num, h = 0;
	while ((1ll<<h) <= p){
		tmp[h++] = t;
		t *= t;
	}
	t = 1;
	rep(i, 0, h){
		if ((p >> i) & 1)
			t *= tmp[i];
	}
	return(t);
}

int main(void){
	while (true){
		cin >> x >> y;
		if (!(x || y))break;
		n = 2;
		m = 0;

		while (((1ll << m)) <= x)m++;

		while (m > 1){
			l = power(n, m);
		//	printf("n:%lld m:%lld l:%lld\n", n, m,l);
			if (l > x||l<0)
				m--;
			else if (l==x&&power(n - 1, m) == y)
				break;
			else n++;
		}
		n--;
		if (m == 1)n = y;
		cats.clear();
		cats.reserve(m);
		cnt = 1;
		ht = x;
		while (ht){
			auto pr = make_pair(cnt, ht);
			cats.push_back(pr);
			cnt *= n;
			ht /= (n+1);
		}
		cnt = 0;
		rep(i, 0u, cats.size())
			cnt += cats[i].first,ht+=cats[i].first*cats[i].second;
		cnt -= cats[cats.size() - 1].first;
		cout << cnt << " " << ht << endl;

	}


	return(0);
}