uva 12119 - The Bells are Ringing(数论+枚举)

本文主要是介绍uva 12119 - The Bells are Ringing(数论+枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 12119 - The Bells are Ringing

题目大意：有三个钟，分别间隔t1，t2，t3秒响一次，0时刻同时响，给定M，问有没又满足的三个数，最小公倍数为M。并且t3-t1<=25

解题思路：因为M为t1，t2，t3的最小公倍数，所以ti一定为M的因子，所以只要枚举因子判断即可。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 1e6;
typedef long long ll;ll N;
int tot, num[maxn+5];
int np, prime[maxn+5], vis[maxn+5];
int nf, fact[maxn+5], cnt[maxn+5];void prime_table (int n) {np = 0;for (int i = 2; i <= n; i++) {if (vis[i])continue;prime[np++] = i;for (int j = i * 2; j <= n; j += i)vis[j] = 1;}
}void div_factor (ll n) {nf = 0;memset(cnt, 0, sizeof(cnt));for (int i = 0; i < np; i++) {if (n % prime[i] == 0) {fact[nf] = prime[i];while (n % prime[i] == 0) {n /= prime[i];cnt[nf]++;}nf++;}}if (n > 1) {fact[nf] = n;cnt[nf++] = 1;}
}void dfs (int d, ll u) {if (u > 1000000LL)return;if (d == nf) {num[tot++] = u;return;}for (int i = 0; i <= cnt[d]; i++) {dfs(d+1, u);u *= fact[d];}
}ll gcd (ll a, ll b) {return b == 0 ? a : gcd(b, a % b);
}ll lcm (ll a, ll b) {ll d = gcd(a, b);return a / d * b;
}int main () {int cas = 1;prime_table(maxn);while (scanf("%lld", &N) == 1 && N) {int ret = tot = 0;printf("Scenario %d:\n", cas++);div_factor(N);dfs(0, 1);sort(num, num + tot);for (int i = 0; i < tot; i++) {for (int j = i + 1; j < tot; j++) {if (num[j] - num[i] > 25)break;ll d = lcm(num[i], num[j]);for (int k = j + 1; k < tot; k++) {if (num[k] - num[i] > 25)break;if (lcm(d, num[k]) == N) {printf("%d %d %d\n", num[i], num[j], num[k]);ret++;}}}}if (ret == 0)printf("Such bells don't exist\n");printf("\n");}return 0;
}