暴力枚举
任何一个数都可以分解为合数和素数,合数又可以分解为素数,所以素数打好表分解素数,利用定理即可
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt, tt = 1;
int n;
bool st[N];
inline void init(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++] = i;
for (int j = 0; primes[j] * i <= n; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
inline void solve()
{
int a, b, res = 1;
scanf("%lld %lld", &a, &b);
if (b * b > a)
{
cout << "Case " << tt ++ << ": 0" << endl;
return;
}
int cntx = a;
for (int i = 0; primes[i] * primes[i] <= a; i ++ )
{
int p = primes[i];
int s = 0;
if (a % p == 0)
{
while (a % p == 0) s ++, a /= p;
res *= (s + 1);
}
}
if (a > 1) res *= 2;
res /= 2;
for (int i = 1; i < b; i ++ )
if (cntx % i == 0) res --;
cout << "Case " << tt ++ << ": " << res << endl;
}
signed main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
int t = 1;
scanf("%lld", &t);
init(N);
while (t -- ) solve();
return 0;
}