SDSC2021 Day1
2022/7/9 23:54:11
本文主要是介绍SDSC2021 Day1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
又是一年SDSC到但是我已经成为时代的眼泪啦
但我翻翻去年的笔记,好像就Day1写得还行,剩下几天就很摸
所以就只把Day1的笔记搬过来啦~(我才不会说临时起意搬笔记的原因是又有好题图了(当然不是))
配套题单
质数筛
提供一种快速的分解质因数的方法:
在线性筛的时候可以顺道求出每个数的最小的质因数,方法如下:
void init_P(){ long long i,j; for(i=2;i<=N;i++){//N 是最大筛到的数 if(!mf[i]){//mf 记录最小质因数,同时可以用于判断该数是否被筛过 mf[i]=i; p[++tot]=i; } for(j=1;j<=tot && i*p[j]<=N;j++){ mf[p[j]*i]=p[j];//根据线性筛的性质,每个合数会被自己最小的质因子筛到 if(i%p[j]==0) break; } } }
在求出每个数的最小的质因子后,我们可以进行快速质因数分解。
假如我们要对 \(x\) 进行分解质因数,我们可以提取出它的最小质因数作为一个分解出的因数,并 \(x:=x/mf_x\) 继续进行分解直至 \(x<1\)。
void init_F(int x){ int i,j,u=x,v; while(u>1){ ans[++cnt]=mf[u]; u/=mf[u]; } }
- P1445 [Violet]樱花
神奇推式子题。
\[\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\Leftrightarrow \frac{xy}{x+y}=n! \Leftrightarrow xy-(x+y)n!=0 \Leftrightarrow (n!)^2+xy-(x+y)n!=(n!)^2 \Leftrightarrow \]\[(x-n!)(y-n!)=(n!)^2 \]所以答案就是 \((n!)^2\) 的因子个数。
怎么算呢?考虑唯一分解 \(n!=\sum p_i^{e_i}\)
有 \((n!)^2=\sum p_i^{2e_i}\)。
然后就指数加一连乘积啦~
怎么唯一分解 \(n!\) 呢?
线性筛求 \(p_i\)。对于求 \(e_i\),有公式 \(e_i=\sum\limits_{k \ge 0,p_i^k \le n}\lfloor \frac{n}{p_i^k} \rfloor\);或者在线性筛进行质因数分解(就是一开始写的那个方法)。
代码使用线性筛分解质因数:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const long long mod=1e9+7; long long n,t,p[1000010],mf[1000010],e[1000010],tot,ans; int main(){ long long i,j,u,v; cin>>n; for(i=2;i<=n;i++){ if(!mf[i]){ mf[i]=i; p[++tot]=i; } for(j=1;j<=tot && i*p[j]<=n;j++){ mf[p[j]*i]=p[j]; if(i%p[j]==0) break; } } for(i=2;i<=n;i++){ for(j=i;j>1;j/=mf[j]){ e[mf[j]]++; } } ans=1; for(i=1;i<=n;i++){ ans*=(2*e[i]+1); ans%=mod; } cout<<ans<<endl; return 0; }
GCD&LCM
- P1072 [NOIP2009 提高组] Hankson 的趣味题
暴力可过。
正解见花神的题解。
- CF1334E Divisor Paths
感性理解路径一定是 \(u\to gcd(u,v) \to v\)。根据排列组合,唯一分解 \(x=\sum p_i^{e_i}\) 后,\(x \to 1\) 的路径条数为:\(\frac{(\sum e_i)!}{\prod e_i!}\)。
我们把 \(u,v\) 除以其最大公约数 \(g\),转化为 \(dis(\frac{u}{g},1)\times dis(\frac{v}{g},1)\),即可求解。
还有就是注意由于所有数都是 \(d\) 的因子,所以质数表可以直接在 \(d\) 的因子里筛。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const long long mod=998244353; long long n,t,fac[110],tot,ans; long long p[700010]; inline long long fast(long long a,long long b){ if(b==0) return 1%mod; if(b==1) return a%mod; long long s=fast(a,b/2)%mod; if(b&1) return s*s%mod*a%mod; return s*s%mod; } inline void init_fac(){ long long i; fac[0]=1; for(i=1;i<=100;i++){ fac[i]=fac[i-1]*i%mod; } } inline void init_pri(){ long long d=n,i,sd=sqrt(d); for(i=2;i<=sd;i++){ while(d%i==0){ p[++tot]=i; d/=i; } } if(d>1) p[++tot]=d; } inline long long gcd(long long a,long long b){ if(b==0) return a; return gcd(b,a%b); } inline long long sol(long long u){ if(u==1) return 1; long long i,cnt=0,cntt=0,on,down=1; for(i=1;i<=tot;i++){ cnt=0; while(u%p[i]==0){ cnt++; u/=p[i]; } down*=fac[cnt];down%=mod; cntt+=cnt; } on=fac[cntt]; return on*fast(down,mod-2)%mod; } int main(){ long long i,j,u,v; cin>>n>>t; init_fac(); init_pri(); while(t--){ scanf("%lld %lld",&u,&v); if(u==v){ cout<<1<<endl; continue; } j=gcd(u,v); printf("%lld\n",sol(u/j)*sol(v/j)%mod); } return 0; }
进制转换
- CF1114C Trailing Loves (or L'oeufs?)
扩展欧几里得
裴蜀定理
不定方程 \(ax+by=m\) 有整数解的充要条件是 \(\gcd(a,b) \mid m\)
引理1(其实就是余数的定义):\(a \mod b=a- \lfloor \frac{a}{b} \rfloor \times b\)
设 \(d=\gcd(a,b)\),exgcd 可给出不定方程 \(ax+by=d\) 的一组特解 \((x_0,y_0)\)。
记 \(ax_1+by_1=d\)
设 \(a'=b,b'=a \mod b\),则有 \(a'x_2+b'y_2=d\)
所以 \(ax_q+by_1=a'x_2+b'y_2\)
根据引理,有 \(ax_1+by_1=bx_2+(a- \lfloor \frac{a}{b} \rfloor \times b)y_2\)
整理得 \(ax_1+by_1=ay_2+b(x_2- \lfloor \frac{a}{b} \rfloor y_2)\)
因为恒等,所以 \(x_1=y_2,y_1=x_2-\lfloor \frac{a}{b} \rfloor y_2\)
故,可以代入 \(x_2,y_2\) 递归求解直至 \(y_2=0\) 返回 \(x=1,y=0\) 回溯回去。
int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1;y=0; return a; } int t,ans; ans=exgcd(b,a%b,x,y); t=x; x=y; y=t-(a/b)*y; return ans; }
欧拉函数
定义:\(\phi(x)=[1,x]\) 中与 \(x\) 互质的数的个数。
性质:设 \(x=\prod p_i^{e_i}\),则 \(\phi(x)=x \prod \frac{p_i-1}{p_i}\)
欧拉定理
若 \(\gcd(a,m)=1\),则 \(a^{\phi(m)} \equiv 1 \pmod m\)
- P2158 [SDOI2008]仪仗队
考虑一个人 \((x,y)\) 可以被看到,当且仅当 \(\gcd(x,y)=1\)。所以答案就是 \((2\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i}[\gcd (i,j)=1])+1=2\sum\limits_{i=1}^{n}\phi(i)+1\)(最后加个 1 的原因是对角线可以看到一个)。
然后欧拉函数可以线性推,不过这题没必要,一般的根号筛法即可。
扩展欧拉定理
\(\forall b \ge \phi(m),a^b \equiv a^{b \mod \phi(m)+\phi(m)} \pmod m\)
- P4139 上帝与集合的正确用法
根据扩展欧拉定理,\(2^{2^{2^{\cdots}}} \mod p=2^{2^{2^{2^{\cdots}}} \mod \phi(p)+ \phi(p)}\)
然后这个东西显然可以递归做。
本题需要用线性筛欧拉函数,方法见下:
在线性筛中,每一个合数都会被自己的最小质因子筛掉。记合数 \(n\) 的最小质因子是 \(p_1\),记 \(n'=\frac{n}{p_1}\)。
-
如果 \(p_1 \mid n'\),则 \(n'\) 包含 \(n\) 的所有质因子,那么 \(n'\) 含有 \(n\) 的所有质因子,于是有:\(\phi(n)=n \prod\limits_{i=1}^{s}\frac{p_i-1}{p_i}=p_1\times n'\prod\limits_{i=1}^{s}\frac{p_i-1}{p_i}=p_1 \times \phi(n')\)。
-
如果 \(p_1\nmid n'\),则 \(p_1 \bot n'\),由于 \(\phi(x)\) 是积性函数,所以 \(\phi(n)=\phi(p_1)\times \phi(n')=(p_1-1)\times \phi(n')\)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long t,P,p[10000010],tot,phi[10000010]; bool mf[10000010]; void init_phi(){ long long i,j; phi[1]=1; for(i=2;i<=10000000;i++){ if(!mf[i]){ p[++tot]=i; phi[i]=i-1; } for(j=1;j<=tot && i*p[j]<=10000000;j++){ mf[i*p[j]]=1; if(i%p[j]==0){ phi[i*p[j]]=phi[i]*p[j]; break; } else{ phi[i*p[j]]=phi[i]*(p[j]-1); } } } } long long fast(long long a,long long b,long long mod){ if(b==0) return 1%mod; if(b==1) return a%mod; long long s=fast(a,b/2,mod)%mod; if(b&1) return s*s%mod*a%mod; return s*s%mod; } long long solve(long long x){ if(x==1) return 0; return fast(2,solve(phi[x])+phi[x],x)%x; } int main(){ long long i,j,u,v; init_phi(); cin>>t; while(t--){ cin>>P; cout<<solve(P)%P<<endl; } return 0; }
中国剩余定理
设有同余方程组 \(\begin{cases}x \equiv a_1(\mod m_1)\\x \equiv a_2(\mod m_2)\\ \vdots \\x \equiv a_n(\mod m_n)\end{cases}\)
其中 \(m_i\) 两两互质,求最小正整数 \(x\)。
设 \(M= \prod m_i, M_i=\frac{M}{m_i}\)
可以发现,\(m_i \mid M_j = 0\),当且仅当 \(i \ne j\)。
设 \(t_i \equiv M_i^{-1}(\mod m_i)\),则 \(a_it_iM_i \equiv \begin{cases}a_i ,\mod m_i\\0, \space \text{otherwise}\end{cases}\)
因此,\(x_0=a_it_iM_i\) 一定是原方程组的解。
由于 \(m_i\) 两两互质,所以 \(x=M \mod x_0\)。
BSGS
基础版:给定正整数 \(a,b,p\),保证 \(a,p\) 互质,求最小非负整数 \(x\),使得 \(a^x \equiv b \pmod p\)
令 \(x=A \lceil \sqrt{p} \rceil - B\),其中 \(0 \le A,B \le \sqrt{p}\),则有 \(a^{A \lceil \sqrt{p} \rceil - B} \equiv b \pmod p\)。把 \(b\) 移到同余式右面去得:\(a^{A \lceil \sqrt{p} \rceil} \equiv ba^B \pmod p\)。
由于已知 \(a,b\),故可以 \(O(\sqrt{p})\) 枚举 \(ba^B\) 的所有取值,用哈希存下来(map 也行,但是会多一个 \(\log\))。然后 \(O(\sqrt{p})\) 枚举 \(a^{A \lceil \sqrt{p} \rceil}\) 的所有取值,比较两者是否同余,就可以得到所有的 \(x\)。
整除分块
主要解决含有 \(\lfloor \frac{n}{i} \rfloor\) 的求和式子。
引理2:当 \(\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor\) 时,\(j_{\max}=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\)
引理3:\(\forall n \in N_+, |\{ \lfloor \frac{n}{d} \rfloor |d \in N_+,d \le n \}| \le 2 \sqrt{n}\)
证明见 oi-wiki。
- P2261 [CQOI2007]余数求和
根据引理 1,原式可化为 \(G(n,k)=nk-\sum\limits_{i=1}^{n}i \lfloor \frac{k}{i} \rfloor\)
这个求和 \(\sum\limits_{i=1}^{n} \lfloor \frac{k}{i} \rfloor\) 可以整除分块搞。
注意到很多值是一样的,而且呈块分布。左端点 \(l\) 就是上一个块的右端点 +1,根据引理 2,块的右端点 \(r\) 就是 \(\min{(\lfloor\frac{k}{\lfloor\frac{k}{l}\rfloor}\rfloor,n)}\)。
对了,别忘了特判最后那一堆 0 的块(不然会出现除数是 0 的情况),它的右端点是 \(n\)。
ans=n*k; for(l=1;l<=n;l=r+1){ if(k/l!=0) r=min(k/(k/l),n); else r=n; ans-=(((l+r)*(r-l+1)/2)*(k/l)); } cout<<ans<<endl;
积性函数
定义:定义域为 \(N_+\) 的函数 \(f(x)\) 若满足 \(a,b\) 互质时 \(f(ab)=f(a)f(b)\),则称 \(f(x)\) 为积性函数。
显然,若 \(f(x)\) 为积性函数,则有 \(f(1)=1\)。
性质:若 \(f(x)\) 为积性函数,则 \(f(x)=\prod p_i^{e_i}\)
所有积性函数都可以用类似于线性筛的方法求出。
常见积性函数
除数函数 \(\sigma_k(n)=\sum_{d|n}d^k\)
欧拉函数 \(\phi(n)\)
莫比乌斯函数 \(\mu(n)=\begin{cases}1, n=1 \\0, \exists d:d^2 \mid n\\(-1)^{\phi(n)},n=p_1p_2...p_m(p_i \space is \space a \space prime)\end{cases}\)
dalao的博文:https://blog.bill.moe/multiplicative-function-sieves-notes/
这篇关于SDSC2021 Day1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升