已知
一个数可以用有限个质数的乘积得到
思考
对于数a
和b
的最大公约数c
, 对于他们之间质数的次方是否满足$k_c$ = min($k_a$, $k_b$), 和递归写法相比又有什么局限呢?
测试题目最大公约数
非递归实现
#include <iostream>
using namespace std;
const int N = 2000;
int n, m;
int p[N], cnt;
bool st[N];
struct Node {
int p, s;
}fac[3][N];
int idx[3];
int qmi(int a, int b) {
int ans = 1;
while(b) {
if(b & 1) ans *= a;
a *= a;
b >>= 1;
}
return ans;
}
void init() {
for (int i = 2; i < N; i ++) {
if(!st[i]) p[cnt ++] = i;
for (int j = 0; p[j] * i < N; j ++) {
st[i * p[j]] = true;
if (i % p[j] == 0) break;
}
}
}
void get(int n, Node* a, int u) {
for (int i = 0; i < cnt; i ++)
if(n % p[i] == 0) {
int s = 0;
while(n % p[i] == 0) s ++, n /= p[i];
a[idx[u] ++] = { p[i], s };
}
if(n > 1) a[idx[u] ++] = { n, 1 };
// for (int i = 0; i < idx[u]; i ++) cout << a[i].p << ' ' << a[i].s << endl;
// cout << endl;
}
int main() {
init();
cin >> n >> m;
get(n, fac[0], 0);
get(m, fac[1], 1);
for (int i = 0, j = 0; i < idx[0] && j < idx[1]; ) {
int p1 = fac[0][i].p, s1 = fac[0][i].s;
int p2 = fac[1][j].p, s2 = fac[1][j].s;
if(p1 != p2) {
if(p1 < p2) i ++;
else j ++;
}
else {
//cout << p1 << ' ' << p2 << ' ' << min(s1, s2) << endl;
fac[2][idx[2] ++] = { p1, min(s1, s2) };
i ++, j ++;
}
}
int ans = 1;
for (int i = 0; i < idx[2]; i ++) {
//cout << fac[2][i].p << " " << fac[2][i].s << endl;
ans *= qmi(fac[2][i].p, fac[2][i].s);
}
cout << ans << endl;
}
递归
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
}
总结
相比于递归写法快了6ms, 对于做题好像没有任何帮助, 那么对于最小公倍数就是 kc = max(ka, kb)
了
好耶, 无用的知识又增加了