LightOJ 1236

题目描述如下

求 n 以内 lcm( a, b ) = n 的 ab 的对数 保证 a <= b

那么我们就很容易想到因子公式

X = 

 之后就是如果想让两个因子lcm 为 X

那么 对于两个数字 a b（暂且不管 a b大小）

必有 a = 

 , b = 

  假设 ai bi 中的每一个都取得不是最大 那么我们发现这俩东西 lcm 不会是 X 而是一个比 X 小的 X 的因子， 因为 lcd( a b ) = 

  lcm = a * b / lcd( a b )  所以 pi 的系数在a b 中必须有一个 ei 是得取最大的，剩下那个则可以随意去取，

对于 ai == ei 时候， bi 可取 [0 ei] 共 1+ei 个情况

ai < ei 时 bi 只可取 ei , ai 可取 [0, ei) 共  ei 个情况

合起来共有 2ei+1 那么 答案显而易见就是 

 但是还有一个问题

都取 ei 的时候算了1次，而且ab ba是一种情况，所以我们还需要 +1之后再/2（先/2的话会默认向下取整出现问题）

答案就显而易见了。

以下是 AC 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
#define ll long long int
bool is_prime[maxn];
ll prime[maxn/10],tot;
void judge()
{
    memset(is_prime,true,sizeof is_prime);
    tot = 0;
    is_prime[0] = is_prime[1] = false;
    for(ll i=2;i<maxn;i++)
    {
        if(is_prime[i])
        {
            prime[tot++] = i;
            for(ll j=i+i;j<maxn;j+=i)
            {
                is_prime[j] = false;
            }
        }
    }
}
ll slove(ll n)
{
    ll res = 1;
    for(int i=0;i<tot;i++)
    {
        if(n % prime[i] != 0)continue;
        if(prime[i] * prime[i] > n)continue;
        ll k = 0;
        while(n % prime[i] == 0)
        {
            n /= prime[i];
            k ++;
        }
        res *= (k*2+1);
    }
    if(n > 1)
        res *= 3;
    return res;
}
int main()
{
    int t,cas = 1;
    scanf("%d",&t);
    judge();
    while(t--)
    {
        ll n;
        scanf("%lld",&n);
        ll num = slove(n);
        printf("Case %d: %lld\n",cas++,(num+1)/2);
    }
    return 0;
}