每日一题-质因子数量-题解

质因子数量

题目描述

给出n个数字，你可以任意选择一些数字相乘，相乘之后得到新数字x，x的分数等于x不同质因子数量。
请你计算所有选择数字方案中，x分数的总和。答案对1000000007取模。

输入格式

输入第一行为一个正整数 $n$ 。
第二行包含 $n$ 个正整数ai。(1≤n≤200000,1≤ai≤1000000)

输出格式

输出一个整数表示答案。

输入样例

3
6 1 2

输出样例

10

P1780 - [NewOJ Contest 9] 质因子数量

思路

这题很容易想到暴力枚举每一个数相乘的集合，再暴力计算不同质因子的和。但这样的光是枚举的时间复杂度就是 $O(2^n)$ 再计算的话，很容易就TLE了。为此我们不如反过来想想，求出每一个不同的质因子出现的次数，最后求出每个质因数能产生的分数，再累加回来。

根据排列组合的知识我们可以知道，对于一个由 $N$ 个数字组成的集合，可能性一共有 $2^N$ 种。如果求的是由 $N$ 个数字组成的非空集合，可能性一共有 $2^{N}- 1$ 种，也就是所有的组合可能总数减去1个空集。

对于一个已有的质因子 $p$
假设已知含有 $p$ 这个因子的 $a_i$ 有 $k$ 个，
则不含有 $p$ 这个因子的 $a_i$ 有 $n - k$ 个（$n$是数字的个数）

易得，组成一个含有质因子 $p$ 的 $x$ 集合有 $2^{k}- 1$ 种（不算空集 $\emptyset$ ）
则组成一个不含有质因子 $p$ 的 $x$ 集合有 $2^{n-k}$ 种（算空集 $\emptyset$ ）

那么质因子 $p$ 能产生的分数就有 $(2^{k}-1)\times{2^{n-k}}$

由于数据量较大，化简成 $2^{n}-2^{n-k}$ 在计算过程中有炸long long的风险，保险起见不化简了(当然，你可以开个i128试试？)

因此，我们只需要求出质因子的取值范围和含有这个质因子的 $a_i$ 的个数就好了
到此，题目被我们分析成了求质因子的取值范围并求质因子的个数

求一个数的质因子 时间复杂度 $O(\sqrt{n})$

std::vector<i64> getPrimes(i64 value) {
    std::vector<i64> vec(0);
    for (int i = 2; i * i <= value and value > 1; ++i)
        if (not(value % i)) {
	        //这里是一个优化,减少std::move拷贝带来的性能损失
	        //std::vector::push_back方法的push原理如下
	        //--------------------------------------
	        //push_back(value_type&& __x) {
		    //    emplace_back(std::move(__x));
		    //}
		    //--------------------------------------
            vec.emplace_back(i);
            while (not(value % i))
                value /= i;
        }
    //说明数本身就是质数
    if(value > 1)
        vec.emplace_back(value);
    return vec;
}

涉及到幂运算和求模运算，这里直接使用快速幂算法

快速幂 时间复杂度 $O(\log{n})$

i64 powWithMod(i64 base, i64 power, i64 mod) {
    base %= mod;
    i64 res = 1;
    while (power > 0) {
        if(power & 1)
            res = ((res % mod) * (base % mod)) % mod;
        base = ((base % mod) * (base % mod)) % mod;
        power >>= 1;
    }
    return res;
}

完整C with STL代码

#include <vector>
#include <cstdio>
#include <map>
using i64 = long long;
i64 read() {
    i64 data = 0; int c = getchar(); bool f = false;
    while (c < '0' or c > '9') {
        if (c == '-')
            f = true;
        c = getchar();
    }
    while (c >= '0' and c <= '9') {
        data = (data << 3) + (data << 1) + c - '0';
        c = getchar();
    }
    return f ? -data : data;
}

std::vector<i64> getPrimes(i64 value) {
    std::vector<i64> vec(0);
    for (int i = 2; i * i <= value and value > 1; ++i)
        if (not(value % i)) {
            vec.emplace_back(i);
            while (not(value % i))
                value /= i;
        }
    if(value > 1)
        vec.emplace_back(value);
    return vec;
}

i64 powWithMod(i64 base, i64 power, i64 mod) {
    base %= mod;
    i64 res = 1;
    while (power > 0) {
        if(power & 1)
            res = res * base % mod;
        base = base * base  % mod;
        power >>= 1;
    }
    return res;
}

int main() {
    const i64 MOD = 1000000007;
    i64 n = read(), ans = 0;
    std::map<i64, i64> m;
    for(i64 i = 0; i < n; i++) {
        for (i64 j : getPrimes(read()))
            m[j]++;
    }
    for(auto i : m) {
        ans = (powWithMod(2, n - i.second, MOD)
               * (powWithMod(2, i.second, MOD) - 1)
               + ans) % MOD;
    }
    printf("%lld", ans);
    return 0;
}

C++代码（屎山匿名函数代码）

#include <iostream>
#include <map>

using i64 = long long;

int main() {
    const i64 MOD = 1000000007;
    auto read = []() {
        i64 data = 0;
        int c = getchar();
        bool f = false;
        while (c < '0' or c > '9') {
            if (c == '-')
                f = true;
            c = getchar();
        }
        while (c >= '0' and c <= '9') {
            data = (data << 3) + (data << 1) + c - '0';
            c = getchar();
        }
        return f ? -data : data;
    };
    auto powWithMod = [](i64 base, i64 power, i64 mod) {
        base %= mod;
        i64 res = 1;
        while (power > 0) {
            if (power & 1)
                res = res * base % mod;
            base = base * base % mod;
            power >>= 1;
        }
        return res;
    };
    i64 n = read(), ans = 0;
    std::map<i64, i64> m;
    auto getPrimes = [&](i64 value) {
        for (int i = 2; i * i <= value and value > 1; ++i)
            if (not(value % i)) {
                m[i]++;
                while (not(value % i))
                    value /= i;
            }
        if (value > 1)
            m[value]++;
    };
    for (i64 i = 0; i < n; i++)
        getPrimes(read());
    for (auto i: m) {
        ans = (powWithMod(2, n - i.second, MOD)
               * (powWithMod(2, i.second, MOD) - 1)
               + ans) % MOD;
    }
    std::cout << ans;
    return 0;
}

C with STL优化上面C++屎山

#include <cstdio>
#include <map>

using i64 = long long;
const i64 MOD = 1000000007;

i64 read() {
    i64 data = 0;
    int c = getchar();
    bool f = false;
    while (c < '0' or c > '9') {
        if (c == '-')
            f = true;
        c = getchar();
    }
    while (c >= '0' and c <= '9') {
        data = (data << 3) + (data << 1) + c - '0';
        c = getchar();
    }
    return f ? -data : data;
}

i64 powWithMod(i64 base, i64 power, i64 mod) {
    base %= mod;
    i64 res = 1;
    while (power > 0) {
        if (power & 1)
            res = res * base % mod;
        base = base * base % mod;
        power >>= 1;
    }
    return res;
}

i64 n = read(), ans = 0;
std::map<i64, i64> m;

void getPrimes(i64 value) {
    for (int i = 2; i * i <= value and value > 1; ++i)
        if (not(value % i)) {
            m[i]++;
            while (not(value % i))
                value /= i;
        }
    if (value > 1)
        m[value]++;
}

int main() {
    for (i64 i = 0; i < n; i++)
        getPrimes(read());
    for (auto i: m) {
        ans = (powWithMod(2, n - i.second, MOD)
               * (powWithMod(2, i.second, MOD) - 1)
               + ans) % MOD;
    }
    printf("%lld", ans);
    return 0;
}

AC截图