首页 > 代码库 > Hdu 4497

Hdu 4497

2024-07-05 10:42:07   217人阅读

题目链接

已知 gcd(x, y, z) = G, lcm(x, y, z) = L， 求有多少种组合(x, y, z)可以满足条件。G, L都在32位int范围内。

思路： 素数分解 + 容斥

L : p1^t1 * p2^t2 ... * pi^ti

G: q1^s1 * q2^s2... * qi^si

若 L % G 不为0, 则不存在解;

否则 L分解结果中素因子的长度一定不小于G分解结果的素因子个数，

且对应的素数的指数部分前者（L的分解结果）一定不小于后者（G的分解结果）。

比如，对于共同的一个质因子pi, L和G分解结果中对应的指数分别为 b和c， 那么b >= c， 

且三个数（也就是x， y，z）的分解因式中一定有一个pi对应的指数为c， 同时也有一个为c

另一个为b~c中任意一个数。

利用容斥： 结果 = 任意3个b~c中的数的组合个数（即(b-c+1)^3) - 没有出现b的组合个数(即(b-c)^3)

　　　　　　- 没有出现c的组合个数（即(b-c)^3) + 没有出现b也没有出现c的组合个数（(b-c-1)^3).

附上代码：

 1 /*************************************************************************
 2     > File Name: 4497.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年05月20日 星期二 09时40分42秒
 6     > Propose: 素数分解 + 容斥 
 7  ************************************************************************/
 8 
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <vector>
13 #include <fstream>
14 #include <cstring>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 
19 typedef long long LL;
20 typedef pair<int, int> pii;
21 #define X first
22 #define Y second
23 const int MAX_N = (100005);
24 int prime[10000], cnt = 0 // 记录素数;
25 bool vis[MAX_N+1];
26 vector<pii> cnt1, cnt2; // 记录素数分解结果
27 
28 // 素数筛
29 void
30 get_prime() {
31       memset(vis, true, sizeof(vis));
32     for (int i = 2; i < MAX_N; i++) {
33           if (vis[i]) {
34               prime[cnt++] = i;
35               for (LL j = (LL)i*i; j < MAX_N; j += i) {
36                   vis[j] = false;
37             }
38         }
39     }
40 }
41 
42 // 素数分解
43 void
44 split(int n, vector<pii> &ret) {
45       ret.clear();
46       for (int i = 0; i < cnt && prime[i] <= n/prime[i]; i++) {
47           if (n % prime[i] == 0) {
48               int count = 0;
49             while (n % prime[i] == 0) {
50                   count++;
51                 n /= prime[i];
52             }
53             ret.push_back(pii(prime[i], count));
54         }
55     }
56     if (n != 1) {
57           ret.push_back(pii(n, 1));
58     }
59 }
60 
61 int
62 main(void) {
63     //素数筛
64       get_prime();
65     int t;
66     scanf("%d", &t);
67     while (t--) {
68         int G, L;
69           scanf("%d %d", &G, &L);
70           if (L % G) {
71               puts("0");
72             continue;
73         }
74         //素数分解
75           split(G, cnt1);
76         split(L, cnt2);
77         int ans = 1;
78         int len1 = cnt1.size(), len2 = cnt2.size();
79         for (int i = 0, j = 0; i < len1; i++, j++){
80               while (cnt1[i].first != cnt2[j].first) {
81                   j++;
82             }
83             cnt2[j].second -= cnt1[i].second;
84         }
85         for (size_t i = 0; i < len2; i++) {
86             if(cnt2[i].second == 0) {
87                 ans += 0;
88             } else {
89                 int c = cnt2[i].second;
90                 //容斥
91                 ans *= ((LL)c+1)*(c+1)*(c+1) - 2*((LL)c)*(c)*(c) + ((LL)c-1)*(c-1)*(c-1);
92             }
93         }
94         printf("%d\n", ans);
95     }
96 
97     return 0;
98 }

 


联系
我们