多少个约数-阿里云开发者社区

多少个约数

2022-12-04 78

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 多少个约数

问题描述

给定正整数 a, b, c，请问有多少个正整数，是其中至少两个数的约数。

输入格式

输入一行包含三个正整数 a, b, c。

输出格式

输出一行包含一个整数，表示答案。

样例输入

30 70 35

样例输出

样例说明

1、2、5、7、10、35满足条件。

评测用例规模与约定

对于 50% 的评测用例，1 <= a, b, c <= 1000000。

对于所有评测用例，a, b, c 不超过 10**12（10的12次方）。

大致思路

首先进行分解质因数，存入map中。然后利用容斥原理，可以得到如下表达式（Q a . . b 表示a…b的公约数数量）

可求出答案数。

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    map<ll, ll> sa, sb, sc;
    for (int i = 2; i <= a && a != 1; i++) {
        while (a % i == 0) {
            sa[i]++;
            a = a / i;
        }
    }
    for (int i = 2; i <= b && b != 1; i++) {
        while (b % i == 0) {
            sb[i]++;
            b = b / i;
        }
    }
    for (int i = 2; i <= c && c != 1; i++) {
        while (c % i == 0) {
            sc[i]++;
            c = c / i;
        }
    }
    ll cab = 0, cbc = 0, cac = 0, cabc = 0;
    for (map<ll, ll>::iterator it = sa.begin(); it != sa.end(); it++) {
        cab += min(it->second, sb[it->first]);
        cac += min(it->second, sc[it->first]);
        cabc += min(min(it->second, sc[it->first]), sb[it->first]);
    }
    for (map<ll, ll>::iterator it = sb.begin(); it != sb.end(); it++) {
        cbc += min(it->second, sc[it->first]);
    }
    cout << pow(2, cab) + pow(2, cac) + pow(2, cbc) - 2 * pow(2, cabc) << endl;
    return 0;
}