QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726590 | #8339. Rooted Tree | beamishboys# | TL | 0ms | 0kb | C++23 | 1.5kb | 2024-11-09 03:16:17 | 2024-11-09 03:16:18 |
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