PKU 3175 Finding Bovine Roots

• 二分探索
• 整数部分を固定すると、小数部分は単調増加になる
• 整数部分をループで回して二分探索をすると通る

long double TENS = 1.0;
int saturate(long double value) {
	value -= (int)value;
	value *= TENS;
	return (int)value;
}

int main() {
	int L;
	cin >> L;
	REP(i, L) {
		TENS *= 10.0;
	}

	int value;
	cin >> value;
	for (int i = 1; ; ++i) {
		ll lower = i;
		lower *= lower;
		ll upper = i + 1;
		upper *= upper;

		// 整数用二分探索
		ll l = lower;
		ll r = upper;
		while (l + 1 < r){
			ll M = (l + r) / 2;
			if (saturate(sqrt((long double)M)) <= value){
				l = M;
			} else {
				r = M;
			}
		}

		if (value == saturate(sqrt((long double)l))) {
			cout << l << endl;
			return 0;
		}
	}
}