数论 Level2
说明
- 也是因为内容量过大，只保留自己不太会的部分
qwq
数论分块
- 数论分块：OI-Wiki
定义所有的二元组 (1,k) 是好的，如果二元组 n,k 是好的则二元组 (n + k),(nk,k) 是好的，输入 N,K，求 1\le n\le N,1\le k\le K 的好的二元组。 1\le N\le 10^{12},1\le K\le 10^{12}
排列组合
二项式定理
- 证明：(a+b)^n=(a+b)\times(a+b)\times\dots\times(a+b)\\ \sum_{i=0}^n a^i\times b^{n-i}\times C_n^i
有用的东西
x_1+x_2+x_3+\dots+x_n=T ，要求 x_i\ge0
求方案数
- 可以把原式转化为 (x_1+1)+(x_2+1)+\dots+(x_n+1)=T+n
- 条件转化为 x_i\ge1
- 就可以对 T+n 进行插板，插 n-1 个板子
- 方案数就是 C^{n-1}_{T+n-1}
课后题
毕业季
-
很人类智慧的一道题 -
对于整数序列 1,2,\dots,n ，我们要选择 k 个数，这 k 个数的最大公约数即为默契程度
-
假设选中的 k 个数中的最大公约数为 d ，那么每个选中的书都可以被 d 整除
-
由于选择的 k 个数是连续的，且从 1 开始递增，所以这 k 个数可以表示为： d,2d,3d,\dots,kd
-
根据题目要求，这 k 个数必须在 1 到 n 之间。因此， kd 必须小于等于 n ，即 kd\le n ，即 d\le \lfloor\frac{n}{k}\rfloor
-
所以最大答案就是
n/k#include<bits/stdc++.h> using namespace std; int main() { int n,k; scanf("%d%d",&n,&k); printf("%d",n/k); return 0; }
因子个数和
-
代码就是数论分块的板子，但怎么推出来的是个问题
-
一个数的因子是成对出现的，例如若 x 是 n 的因子，则 \frac{n}{x} 也是 n 的因子
-
可以将因子分为两类：小于等于 \sqrt{n} 的因子和大于 \sqrt{n} 的因子
-
然后就可以用数论分块来做了，时间复杂度 O(\sqrt{n})
#include<bits/stdc++.h> #define int long long using namespace std; int n,k; int fun(int l,int r) { return r - l + 1; } int Solve() { int l = 1, r = 0, res = 0; while (l <= n) { r = k / (k / l); res += fun(l,r) * (k / l); l = r + 1; } return res; } signed main() { scanf("%lld",&n); k = n; printf("%lld",Solve()); }
完全平方数
-
完全平方数在分解质因数后其相同质因数的数量一定是偶数
-
所以考虑枚举 [1,n] 之间可能的质因子，并计算出这个质因子在 [1,n] 范围内有多少个
-
如果质因子的数量不是偶数，就把数量 -1
-
为什么这么做没错？
-
假设我们枚举的质因子为 7 ，在 [1,21] 内有 3 个 7：
7=7,14=2\times7,21=3\times7 -
此时发现质因数 7 有 3 个，就可以把质因子 7 自己丢掉，不把他乘进答案里
-
最终乘进答案里的包含质因数 7 的数就有
14,21 -
减一操作就是这个意思
#include <bits/stdc++.h> #define ll long long using namespace std; const int P = 100000007, maxn = 5000005, maxm = 50000005; int a[maxn], n, tot; ll p[maxn], ans = 1; bool vis[maxm]; ll qp(ll x,int y) { ll res = 1; while (y > 0) { if (y & 1) res = res * x % P; x = x * x % P, y >>= 1; } return res; } int main() { scanf("%d",&n); vis[1] = true, vis[2] = false; for (int i = 2; i <= (n >> 1) + (n & 1); i ++) // 枚举n中可能的质因子 if (!vis[i]) { a[++ tot] = 0; // 是质数 for (int j = 1; j * i <= n; j++) { // 分解质因数 int now = j; a[tot] ++; while (now % i == 0) a[tot] ++, now /= i; // 统计质因子 i 有多少个 vis[j * i] = 1; // 标记为已经计算过 } a[tot] -= a[tot] & 1, p[tot] = qp(i,a[tot]);// 如果不被2整除则减掉 i 自己以保证最终可以形成一个完全平方数 } for (int i = 1; i <= tot; i++) ans = ans * p[i] % P; // 统计答案 printf("%lld",ans); return 0; }
寒风农场
-
题目问你
a+(a\ \operatorname{mod}\ n)+((a+(a\ \operatorname{mod}\ n))\ \operatorname{mod}\ n)+\dots -
这个式子什么时候是 n 的倍数
-
就等于问你
(a+(a\ \operatorname{mod}\ n)+((a+(a\ \operatorname{mod}\ n))\ \operatorname{mod}\ n)+\dots)\ \operatorname{mod}\ n -
这个式子什么时候等于 0
-
就等于问你
(a+a^2+a^4+a^8+\dots)\ \operatorname{mod}\ n -
这个式子什么时候等于 0
-
然后暴力就行了
#include<bits/stdc++.h> #define ll long long #define int long long using namespace std; int T,a,n; bool check(int x) { ll k = 1; if (x == 0) return false; while (k <= x) { if (k == x) return true; k *= 2; } return false; } signed main() { scanf("%lld",&T); for (int i = 1;i <= T;i ++) { scanf("%lld%lld",&a,&n); bool ok = true; for (int j = 1;j <= 30;j ++) { if (a % n == 0) { printf("Yes\n"); ok = false; break; } a *= 2; } if (ok) printf("No\n"); } }
CQOI余数之和
-
也是数论分块
-
假设 n = 5,k = 3
-
那 j(n,k) 就等于
3\ \operatorname{mod}\ 1+3\ \operatorname{mod}\ 2+3\ \operatorname{mod}\ 3+3\ \operatorname{mod}\ 4+3\ \operatorname{mod}\ 5 -
等价于
(3-\lfloor\frac{3}{1}\rfloor\times3)+(3-\lfloor\frac{3}{2}\rfloor\times2)+(3-\lfloor\frac{3}{3}\rfloor\times3)+\dots -
把 3- 都提出来，原式等于
3\times5-(\lfloor\frac{3}{1}\rfloor\times3)-\dots -
后面 \lfloor\frac{k}{i}\rfloor 可以用数论分块 O(\sqrt{n}) 求解
#include<bits/stdc++.h> #define int long long using namespace std; int n,k; int fun(int l,int r) { return ((l + r) * (r - l + 1)) >> 1; } int Solve() { int l = 1, r = 0, res = 0; while (l <= n) { if (k / l) r = min(n, k / (k / l)); else r = n; res += fun(l,r) * (k / l); l = r + 1; } return res; } signed main() { scanf("%lld%lld",&n,&k); printf("%lld",n * k - Solve()); }
基因序列
-
感谢 Syxqwq 神犇提供的思路 %%%
对于每个 a_i 分解质因子，其中这步可以 O(n) 预处理然后 O(n\log n) 求出，也可以 O(n\sqrt{n}) 求。
然后对于从根节点出发，用
stack记录某个质因子最后一次出现到了哪里，然后每个节点对着分解后的质因子求最近的就行，dfs完回溯。 -
但是 O(n) 的线性筛预处理会被卡 qwq
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5,maxm = 2e6 + 5;
int fa[maxn], n, q, a[maxn], ans[maxn], depth[maxn], ansdep[maxn];
vector<int> num[maxn], st[maxm], mp[maxn]; int tot,p[maxm << 1]; bool vis[maxm << 1];
void addEdge(int u, int v) { mp[u].push_back(v); }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void Union(int u,int v) { fa[find(v)] = find(u); }
void dfs(int u, int dep) {
depth[u] = dep;
for (auto v : num[u]) {
if (!st[v].empty() && ansdep[u] < depth[st[v].back()]) {
ansdep[u] = depth[st[v].back()];
ans[u] = st[v].back();
}
st[v].push_back(u);
}
for (auto v : mp[u]) dfs(v, dep + 1);
for (auto v : num[u]) st[v].pop_back();
}
bool check(int x) {
if (x <= 1) return false;
for (int i = 2;i * i <= x;i ++)
if (x % i == 0) return false;
return true;
}
int main(){
scanf("%d%d",&n,&q);
for (int i = 1,k; i <= n; i ++) {
fa[i] = i, ans[i] = -1; scanf("%d",&a[i]); k = a[i];
for (int x = 2;x * x <= k; x ++) {
if (!check(x) || a[i] % x != 0) continue;
while (a[i] > 1 && a[i] % x == 0) a[i] /= x;
num[i].push_back(x);
}
if (a[i] > 1) num[i].push_back(a[i]);
}
for (int i = 1, x, y; i < n; i ++) {
scanf("%d%d",&x,&y);
addEdge(x, y); Union(x,y);
}
for (int i = 1; i < n; i ++)
if (fa[i] == i) dfs(i, 1);
for (int i = 1,u;i <= q;i ++) {
scanf("%d",&u);
printf("%d\n",ans[u]);
}
return 0;
}