问题描述
给定正整数 a, b, c，请问有多少个正整数，是其中至少两个数的约数。
输入格式
输入一行包含三个正整数 a, b, c。
输出格式
输出一行包含一个整数，表示答案。
样例输入
30 70 35
样例输出
6
样例说明
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; }
