跳转至

数学-因数分解

质因数分解

  • Project Euler #3: Largest prime factor（质因数分解，求最大质因数）
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


long long maxFactor(long long n)
{
    long long res = 2;
    while (!(n & 1)) n >>= 1;
    if (n == 1) return res;

    long long limit = sqrt(n) + 1;
    for (long long i = 3; i <= limit; i += 2) {
        while (n != i) {
            if (n % i == 0) {
                res = max(res, i);
                n /= i;
            }
            else break;
        }
    }
    res = max(res, n);

    return res;
}


int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    long long n;
    while (caseNum--) {
        cin >> n;
        cout << maxFactor(n) << endl;
    }


    return 0;
}

因数分解

给出一个正整数aa，要求分解成若干个正整数的乘积，即a=a1×a2×a3×...×an，并且1<a1≤a2≤a3≤...≤an，问这样的分解的种数有多少。注意到a=a也是一种分解。

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int calculate(int n, int pre)
{
    if (n < 2 || n < pre) return 0;

    int cnt = 0;
    int limit = sqrt(n);
    for (int i = pre; i <= limit; ++i) {
        if (n % i == 0) {
            cnt += calculate(n / i, i);
        }
    }
    ++cnt; //加上自己

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        int n; cin >> n;
        cout << calculate(n, 2) << endl;
    }

    return 0;
}

因为分解的因数是单增的，所以只需要考察\sqrt n的左半部分即可。

因数分解的指数表示

输入一个数，输出其素因子分解表达式。表达式中各个素数从小到大排列。

如果该整数可以分解出因子a的b次方，当b大于1时，写做 a^b ；当b等于1时，则直接写成a。

比如：

60
2^2*3*5

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

void solve(int n)
{
    vector<int> num;
    for (int i = 2; i <= n; ++i) {
        while (n % i == 0) {
            num.push_back(i);
            n /= i;
        }
    }

    if (num.size() <= 1) { //本身是质数，可能size为0，比如1
        cout << n << endl; return;
    }

    map<int, int> m;
    for (size_t i = 0; i < num.size(); ++i) {
        ++m[num[i]];
    }
    //for (auto e : m) cout << e.first << " " << e.second << endl;

    map<int, int>::iterator it = m.begin();
    while (it != m.end()) {
        int digit = it -> first, cnt = it -> second;
        if (cnt == 1) cout << digit;
        else cout << digit << "^" << cnt;
        ++it;
        if (it != m.end()) cout << "*";
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    solve(n);

    return 0;
}

最小因式分解

给定一个正整数 a，找出最小的正整数 b 使得 b 的所有数位相乘恰好等于 a。

如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。

class Solution {
public:
    int smallestFactorization(int a) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (a < 10) return a; //只有一位数字直接返回

        int n = a;
        string res;
        for (int i = 9; i >= 2; --i) {
            while (n % i == 0) {
                res += to_string(i);
                n /= i;
            }
        }
        if (n != 1) return 0; //如果n最终不为1，则是质数

        reverse(res.begin(), res.end());
        if (res.size() > 9) return 0;
        long long digit = stoll(res);
        if (digit > INT_MAX) return 0;
        return digit;
    }
};

为了让最终的结果最小（现在只考虑结果存在的情况），那么位数越少越好，为了让位数越少，那么最优策略就是让每一位的数字尽可能的大一些，所以从因子9开始。因为要求的是最终结果的每一位乘积与数字a相等，那么每一个被分解到结果的因子都不能超过9.所以最后如果分解完a不为1，那么结果肯定不存在。

求质因子的总和

  • LeetCode 650 只有两个键的键盘

最初在一个记事本上只有一个字符 A。你每次可以对这个记事本进行两种操作：

  • Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
  • Paste(粘贴) : 你可以粘贴你上一次复制的字符。

给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出**恰好** n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。

还可以考虑《数论——反素数》的求因子和的另一个办法

相当于求所有质因子的和。

考虑经过一系列操作使得出现n个A，可以把这一系列过程写成字母表示，比如n = 3的时候：

CPP 代表复制一次，拷贝两次

那么得到最终的结果n，假设经过下列操作：

CPP     CPP...PPP   CPPP...PPP

我们把上面进行分组，每个组里面就是一次C，多次P，设每个组的长度为l_i，则显然有： $$ n = l_1 \times l_2 \times l_3 \cdots \times l_n $$ 则总的操作次数是\sum_{i=0}^n l_i。现在需要考虑l_i怎么划分，如果n是质数，显然一个一个的打印是最快的，最少操作数就是n，如果是合数，那么存在n = p \times q，显然p \geq 2, q \geq 2。则显然有： $$ (p - 1) \times (q - 1) \geq 1 \\therefore p + q \leq p \times q $$ 如果因子p或q还可以继续分解，那么根据上面的推导，操作数还是会进一步的减小，那么当变成质因子的时候，将无法分解，假设质因子是k，则操作代表1次赋值，k - 1次粘贴。

所以最终的结果就是所有质因子的和。

class Solution {
public:
    int minSteps(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int cnt = 0;
        for (int i = 2; i <= n; ++i) {
            while (n % i == 0) {
                cnt += i;
                n /= i;
            }
        }

        return cnt;
    }
};

典型题目：

  • SJTU OJ 4039 质因数分解
  • SJTU OJ 1020 分解质因数
  • 一本通-1210：因子分解
  • LeetCode 625 最小因式分解
  • 洛谷P1075 质因数分解（大水题）
  • 洛谷P2043 质因子分解 (大水题)