QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726590#8339. Rooted Treebeamishboys#TL 0ms0kbC++231.5kb2024-11-09 03:16:172024-11-09 03:16:18

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 03:16:18]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-09 03:16:17]
  • 提交

answer

#pragma GCC optimize "Ofast"
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ull = unsigned long long;
ull inf = 1e19;

const inline ull pow3(ull n) {
	if (n*n >= (inf/n)) return inf;
	return n*n*n;
}
const inline ull pow4(ull n) {
	if (n*n >= (inf/(n*n))) return inf;
	ull a = (n*n);
	return a*a;
}
const inline ull pow(ull n, ull p) {
	if (p == 2) return n*n;
	else if (p == 3) return pow3(n);
	else if (p == 4) return pow4(n);
	ull out = 1;
	while (p-- > 0) {
		if (out >= inf/n) return inf;
		out *= n;
	}
	return out;
}

void solve(ull n, ull k) {
	if (k >= 63) {
		cout << 0 << endl;
		return;
	}
	ull rootk = 1, rootk1 = 1;
	for (int i = 0; i < 200; i++) {
		rootk = (rootk+(n/pow(rootk, k-1)))/2;
		rootk1 = (rootk1+(n/pow(rootk1, k-2)))/2;
	}
	rootk++;
	rootk1++;
	while(pow(rootk-1, k) >= n)rootk--;
	while(pow(rootk1-1, k-1) >= n)rootk1--;
	assert(pow(rootk, k) >= n);
	assert(pow(rootk1, k-1) >= n);
	assert(pow(rootk-1, k) < n);
	assert(pow(rootk1-1, k-1) < n);
	ull out = 0;
	for (ull c = 1; c <= rootk; c++) {
		if (n%c != 0) continue;
		ull lb = 1, ub = rootk1;
		while (lb < ub-1) {
			ull m = (lb+ub)/2;
			ull val = pow(m+c, k);
			if (val == inf) {
				ub = m;
				continue;
			}
			val -= pow(m, k);
			if (val > n) ub = m;
			else if (val <= n) lb = m;
		}
		if (pow(lb+c, k) - pow(lb, k) == n) {
			out++;
		}
	}
	cout << out << endl;
}

int main() {
	int t; cin >> t;
	while (t--) {
		ull n, k; cin >> n >> k;
		solve(n, k);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

6 2

output:


result: