唯一分解定理后的思维题
给我搞成了dfs,但是能过
比较坑的地方是n = i * i这种是不算的
也就是刚好平方根*平方根那种不计入答案,到现在仍然不知道为啥
const int maxn = 1e6 + 10;
int prime[maxn], cnt = 0;
bool isprime[maxn];
void getprime() {
cnt = 0;
for (int i = 2; i < maxn; ++i) {
if (!isprime[i]) prime[cnt++] = i;
for (int j = 0; j < cnt && i * prime[j] < maxn; ++j) {
isprime[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int n, k, ans, cas = 1;
int limit, sqr;
int num[44] = { 0 }, tot = 0;
int cass[44] = { 0 }, to[44];
void dfs(int now, int id, int flag) {
if (now > sqr) return;
if (now >= k && flag) {
ans++;
//printf("%lld\n", now);
}
if (id > limit) return;
int mul = 1;
for (int i = 0; i <= cass[id]; ++i) {
dfs(now * mul, id + 1, i);
mul *= to[id];
}
}
void solve() {
tot = 1;
n = rd(); k = rd();
sqr = sqrt(n);
if (sqr * sqr == n) sqr--;
if (k * k > n) {
printf("Case %lld: 0\n", cas++);
return;
}
int tmp = n;
for (int i = 0; i < cnt; ++i) {
while (tmp % prime[i] == 0) {
if (tmp == 1) break;
num[tot++] = prime[i];
tmp /= prime[i];
}
if (tmp == 1) break;
}
if (tmp != 1) num[tot++] = tmp;
limit = 0;
for (int i = 1; i < tot; ++i) {
if (num[i] == num[i - 1]) cass[limit] ++;
else cass[++limit] = 1, to[limit] = num[i];
}
ans = 0;
dfs(1, 1, 1);
printf("Case %lld: %lld\n", cas++, ans);
}
void solve2() {
n = rd(); k = rd();
if (k * k > n) {
printf("Case %lld: 0\n", cas++);
return;
}
int tmp = n;
int res = 1;
for (int i = 0; i < cnt; ++i) {
int ans = 0;
while (tmp % prime[i] == 0) {
if (tmp == 1) break;
num[tot++] = prime[i];
tmp /= prime[i];
ans++;
}
if (ans) res *= (1 + ans);
if (tmp == 1) break;
}
if (tmp == 1) res /= 2;
for (ll i = 1; i < k; ++i) if (n % i == 0) res--;
printf("Case %lld: %lld\n", cas++, res);
}
signed main() {
//test();
getprime();
int t = 1;
t = rd();
while (t--) solve();
return 0;
}