Pairs Forming LCM

题目

Find the result of the following code:
图片说明
A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).
题意就是，这个函数的复杂度很高，让你写出一个程序来实现同样的功能。

分析

n 是a，b 的最小公倍数
我们可以把a，b进行质因数分解

$a=p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times……….\times p_{n}^{a_{n}}$
$b=p_{1}^{b_{1}} \times p_{2}^{b_{2}} \times……….\times p_{n}^{b_{n}}$
这里，如果有一方没有另一方的某个质因数p，就相当于 $p^{0} = 1$ ,这样便于统一形式
所以：

$gcd(a,b) = p_{1}^{min(a_{1},b_{1})} \times p_{2}^{min(a_{2},b_{2})} \times……….\times p_{n}^{min(a_{n},b_{n})}$
$lcm(a,b) = p_{1}^{max(a_{1},b_{1})} \times p_{2}^{max(a_{2},b_{2})} \times……….\times p_{n}^{max(a_{n},b_{n})}$
而这里lcm(a,b) = n
令 $max(a_{i},b_{i}) = e_{i}$
$n=p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times……….\times p_{n}^{e_{n}}$

计算每一项质因数的幂的方案数：

现在，对于每一项质因数的幂 $p_{i}^{e_{i}}$ ,需要a，b某一方也有 $p_{i}^{e_{i}}$ ,而另一方可以是 $p_{i}^{e_{0～i}}$ (共ei+1)种,然后就是 $C_{2}^{1}\times (e_{i}+1)-1$ ,之所以减一，是因为，当 $a_{i} = bi_{i} = e_{i}$ 时，选谁都一样，不需要 $C_{2}^{1}$

计算总方案数

对于每一种方案数要进行相乘，但是现在题目要求 $lcm(a,b) = n,(a<=b)$ ,所以我们要将总方案数/2+1,加一是因为如果直接除以2，其中有一种方案 $a_{i} = bi_{i} = e_{i}$ a是等于b的，所以除多了，需要加上1

AC代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
const int maxn = 1e7+10;
typedef long long ll;

ll T,N;
ll P[1000010],tail; //1e7之前只有不到1e6的质数，所以这里1e6的空间就够了
bool vis[maxn];//判断是否是质数需要1e7的空间

void init(){
    ll len = (ll)sqrt(maxn)+1;
    for(int i = 2;i<=len;i++){
        if(!vis[i]){
            for(int j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
    for(int i = 2;i<maxn;i++){
        if(!vis[i]) P[tail++] = i;
    }
}

ll solve(ll x){
    ll sum = 1;
    for(int i = 0;i<tail && P[i]*P[i]<=x;i++){
        if(x%P[i] == 0){
            int cnt = 0;
            while(x%P[i] == 0){
                cnt++;
                x/=P[i];
            }
            sum *= 2*(cnt+1)-1;
        }
    }
    if(x>1) sum *= 2*(1+1)-1;
    return sum/2+1;
}

int main(){
    init();
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld",&N);
        printf("Case %d: %lld\n",++kase,solve(N));
    }
    return 0;
}

LightOJ1236-Pairs Forming LCM 【唯一分解定理】

Pairs Forming LCM

题目

分析

计算每一项质因数的幂的方案数：

计算总方案数

AC代码