Day6
T1
没啥玩意好说的，就是别忘删freopen
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
ll a[200005], bj[20000005];
int main()
{
//freopen("a4.in", "r", stdin);
ll ans = 0;
int n = read(), m = read();
for(int i = 1; i<= m; ++ i)a[i] = read();
//sort(a + 1, a + n + 1);
for(int i = 1; i <= m; ++ i)
{
for(ll j = 1; j * a[i] <= n; ++ j)
{
if(bj[j * a[i]] == 0)bj[j * a[i]] = 1, ++ ans;
//if(j % a[i] == 0)break;
}
}
cout << ans;
return 0;
}
T2
我的做法是先欧拉筛一遍找出所有质数，然后埃氏筛一遍找出每个点的 \(fa\)。不过正解是一遍欧拉即可，差别不大，也不难。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);pt('\n');}
int n, q;
int Prime[10000007], fa[10000007], No_Prime[10000007];
int ans[100005];
ll solve(int x, int y)
{
int cnt1 = 0, cnt2 = 0;
while(x != 1)
{
ans[++ cnt1] = x; x /= fa[x];
}
reverse(ans + 1, ans + cnt1 + 1);
while(y != 1)
{
int t = lower_bound(ans + 1, ans + cnt1 + 1, y) - ans;
if(ans[t] == y && t <= cnt1){
return cnt1 - t + cnt2;
}
++ cnt2;
y /= fa[y];
}
return cnt1 + cnt2;
}
int main()
{
int cnt = 0;
n = read(), q = read();
fa[1] = 0;
for(int i = 2; i <= n; ++ i)
{
if(!No_Prime[i])Prime[++ cnt] = i;
for(int j = 1; j <= cnt; ++ j)
{
ll x = Prime[j] * i;
if(x > n)
break;
No_Prime[x] = 1;
if(i % Prime[j] == 0) break;
}
}
for(int i = cnt; i >= 1 ; -- i)
{
for(int j = 1; j <= n; ++ j)
{
if(1ll * Prime[i] * j > n)break;
if(fa[Prime[i] * j] == 0)fa[Prime[i] * j] = Prime[i];
}
}
while(q--)
{
int x = read(), y = read();
if(x > y)swap(x, y);
cout << solve(x, y) << '\n';
}
return 0;
}
T3
易得 \(x+y\) 和 \(x-y\) 奇偶性相同，那我们枚举 \(x-y\)，如果它是偶数，然后那么合法的 \(x+y\) 的个数就是 \(\frac{2n-a}{a}-1\)（下取整），如果是奇数，那么再减去 \(\frac{n-a}{2a}\)（下取整）。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
int n, res;
int main()
{
n = read();
for(int i = 1; i < n; ++ i)
{
res += (2 * n - i) / i - 1;
if(i & 1) res -= (2 * n - i) / (2 * i);
}
cout << res << '\n';
return 0;
}
T4
找出 \(i\) 的所有约数，设其个数为 \(d(i)\) ，其在长度为 \(k\) 的序列中有 \(d(i) ^ k\) 种
但其中有一些序列的最小公倍数会小于 \(j\) 设这些最小公倍数为 \(j\) 则 \(j\) 一定是 \(i\) 的约数
所以继续减去 \(\sum_{j|i, j <i}d(j)^k\)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
int n, k, f[1000005];
const int mod = 998244353;
ll ksm(int x, int k)
{
if(k == 1)return x;
ll t = ksm(x, k / 2);
if(k & 1)return ((t * t) % mod * x) % mod;
return (t * t) % mod;
}
int main()
{
n = read(), k = read();
for(int i = 1; i <= n; ++ i)
{
for(int j = i; j <= n; j += i)
{
++ f[j];
}
f[i] = ksm(f[i], k);
}
for(int i = 1; i <= n; ++ i)
{
for(int j = 2 * i; j <= n; j += i)
{
f[j] = (f[j] - f[i] + mod) % mod;
}
}
for(int i = 1; i <= n; ++ i)cout << f[i] << ' ';
return 0;
}
exgcd
方程 \(xa + yb = g \rightarrow (\gcd(a, b) = g)\)
\(\gcd(b, a \bmod b) = g \rightarrow x'b + y'(a \bmod b) = g\)
\(x'b + y'a - y'b \lfloor\frac{a}{b}\rfloor = g\)
\(y'a + (x' - y' \lfloor\frac{a}{b}\rfloor) \cdot b = g\)
int exgcd(int a, int b, int &x, int &y){
//求g = gcd(a, b)以及 xa + yb = g
if(!b){x = 1, y = 0; return 0;}
int xp, yp;
int g = exgcd(b, a % b, xp, yp);
//xp * b + yp * (a % b) = g
//xp * b + yp * (a - b * (a / b)) = g
//xp * b + yp * a - yp * b * (a / b) = g
//yp * a + (xp - yp *(a/b)) * b = g
x = yp;y = xp - yp * (a / b);
return g;
}
中国剩余定理
法二(ExGcd):
\(x \bmod p_1 = a_1, x \bmod p_2 = a_2, x \bmod p = a\)
设 \(x = k_1 \times p_1 + a_1 = k_2 \times p_2 + a_2\)
\(\therefore k_1 \times p_1 - k_2 \times p_2 = a_2 - a_1\)
void solve(int p1, int a1, int p2, int a2, int &p, int &a){
int g, k1, k2;
g = exgcd(p1, p2, k1, k2);
k2 = -k2;
if((a2 - a1) % g != 0)p = -1, a = -1;
else{
int k = (a2 - a1) / g;
k1 = k1 * k, k2 = k2 * k;
int x = k1 * p1 + a1;
p = p1 / g * p2;
a = (x % p + p) % p;
}
}
费马小定理
若 \(a, p\) 互质且 \(p\) 为质数
\(a^{p-1}\equiv1(\bmod\) \(p)\)
Lucas定理
\(Lucas\) 定理:
先将 \(n, m\) 转换为 \(p\) 进制.
短除法转换进制
如 \(n = 25, m = 12, p = 3\) ,
\(n_{(3)} = 221, m_{(3)} = 110\)
int lucas(int n, int m, int p){
while(n){
++x[0];
x[x[0]] = n % p;
n = n / p;
}//n的p进制表示
while(m){
++y[0];
y[y[0]] = m % p;
m = m / p;
}
int ans = 1;
for(int i = 1; i <= x[0]; ++i)
ans = 1ll * ans * c[x[i]][y[i]] % p;
return ans;
}
int main(){
cin >> n >> m >> p;
for(int i = 0; i <= p; ++i){
c[i][0] = 1;
for(int j = 1; j <= i; ++j){
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
}
}
return 0;
}
\(O(\log n)\)
卢卡斯定理只适用于 \(p\) 为质数, 当 \(p\) 不为质数时, 将其质因数分解
然后中国剩余定理合并, 计算可得
例3
将 \(x\) 拆为 \(k\) 个不同组合数之和
\(x \le 10 ^ 9, k \le 10^3\)
酱汁构造(
数论函数
这玩意该怎么打 \(\LaTeX\) 啊啊啊
鸽了
组合数学
隔板法就是有 \(n\) 个球，用 \(m\) 个板子隔开的方案数，板子不能相邻，也不能在边上
实际就是，有 \(n - 1\) 个空，选 \(m\) 个板子插进去
\(C\binom{n - 1}{m}\)
现在有一个高 \(n\) 宽 \(m\) 的矩阵球从左上到右下的方案数
路径长为 \(n + m -1\)
其中有 \(n\) 步向下
就是从 \(n+m-1\) 步中选 \(n\) 步向下
\(C\binom{n + m - 1}{n}\)