1. 1.Hankson的趣味题
来源:NOIP2009提高组 https://ac.nowcoder.com/acm/contest/257/B
解题思路:
由于 ,因此 一定是 的约数。
所以我们可以枚举 的所有约数,然后依次判断是否满足 以及 即可。
我们可以先预处理出 内的所有质数,然后用这些质数去试除 。分解质因数后,通过DFS枚举出 的所有约数。
时间复杂度:
C++ 代码:
#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef long long LL; typedef pair <int, int> PII; const int N = 45000, M = 50; int primes[N], cnt; bool st[N]; PII factor[M]; int cntf; int divider[N], cntd; void get_primes(int n) { for (int i = 2; i <= n; i++) { if (!st[i]) primes[cnt++] = i; for (int j = 0; primes[j] <= n / i; j++) { st[primes[j] *i] = true; if (i % primes[j] == 0) break; } } } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void dfs(int u, int p) { if (u > cntf) { divider[cntd++] = p; return; } for (int i = 0; i <= factor[u].second; i++) { dfs(u + 1, p); p *= factor[u].first; } } int main() { get_primes(N); int n; scanf("%d", &n); while (n--) { int a0, a1, b0, b1; scanf("%d%d%d%d", &a0, &a1, &b0, &b1); int d = b1; cntf = 0; for (int i = 0; primes[i] <= d / primes[i]; i++) { int p = primes[i]; if (d % p == 0) { int s = 0; while (d % p == 0) s++, d /= p; factor[++cntf] = { p, s }; } } if (d > 1) factor[++cntf] = { d, 1 }; cntd = 0; dfs(1, 1); int res = 0; for (int i = 0; i < cntd; i++) { int x = divider[i]; if (gcd(x, a0) == a1 && (LL) x *b0 / gcd(x, b0) == b1) { res++; } } printf("%d\n", res); } return 0; }
2. 计算系数
来源:NOIP2011提高组 https://ac.nowcoder.com/acm/contest/259/A
算法知识点: 组合数,二项式定理
复杂度:
解题思路:
由二项式定理:
因此, 的系数是 。
时间复杂度分析:
计算的瓶颈在计算 上,对于分母中每个数都需要做一次快速幂,因此总时间复杂度是 。
C++ 代码:
#include <iostream> #include <algorithm> using namespace std; const int mod = 10007; int qmi(int a, int k) { a %= mod; int res = 1; while (k) { if (k &1) res = res *a % mod; a = a *a % mod; k >>= 1; } return res; } int main() { int a, b, k, n, m; cin >> a >> b >> k >> n >> m; int res = qmi(a, n) *qmi(b, m) % mod; for (int i = 1, j = k; i <= n; i++, j--) { res = res *j % mod; res = res *qmi(i, mod - 2) % mod; } cout << res << endl; return 0; }
3. 组合数问题
来源:NOIP2016提高组 https://ac.nowcoder.com/acm/contest/264/A
算法知识点: 前缀和,组合数
复杂度:
解题思路:
首先通过组合恒等式 将所有 模 的余数预处理出来。
然后递推出前缀和:s[i][j]
,表示 中 的倍数的个数。
查询时直接查表即可。
C++ 代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 2010; int c[N][N]; int s[N][N]; int main() { int T, k; scanf("%d%d", &T, &k); for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++) { if (!j) c[i][j] = 1 % k; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k; if (!c[i][j]) s[i][j] = 1; } for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { if (i) s[i][j] += s[i - 1][j]; if (j) s[i][j] += s[i][j - 1]; if (i && j) s[i][j] -= s[i - 1][j - 1]; } while (T--) { int n, m; scanf("%d%d", &n, &m); printf("%d\n", s[n][m]); } return 0; }
4. 小凯的疑惑
来源:NOIP2017提高组 https://ac.nowcoder.com/acm/contest/265/D
算法知识点: 数论
时间复杂度:
解题思路:
结论题:
如果 均是正整数且互质,那么由 不能凑出的最大数是 。
C++ 代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; int main() { LL a, b; cin >> a >> b; cout << a *b - a - b << endl; return 0; }
另外,牛客暑期NOIP真题班限时免费报名
报名链接:https://www.nowcoder.com/courses/cover/live/248
报名优惠券:DCYxdCJ