Day 1
数论
扩展欧几里得算法
求 \(\gcd(a,b)\) 同时求出关于 \(x,y\) 的方程 \(ax+by=\gcd(a,b)\) 的一组整数解。
首先，当 \(b=0\) 时，原方程变为 \(ax=|a|\)，解得 \(x=\pm1\) 且 \(y\) 为任意整数。
设 \(\gcd(a,b)=\gcd(b,a\bmod b)=bx'+(a\bmod b)y'\)，又有 \(a\bmod b=a-\left\lfloor\dfrac{a}{b}\right\rfloor\cdot b\)，所以
又因为 \(ax+by=\gcd(a,b)\)，所以 \(x=y',y=(x'-\left\lfloor\dfrac{a}{b}\right\rfloor\cdot y')\)。具体实现时递归求解即可。
代码：
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(b==0){x=1,y=0;return a;}ll xx,yy;ll g=exgcd(b,a%b,xx,yy);x=yy;y=xx-a/b*yy;return g;
}
乘法逆元
如果存在 \(ax\equiv1\pmod m\)，则称 \(x\) 为 \(a\) 模 \(m\) 下的乘法逆元。\(a\) 模 \(m\) 下有乘法逆元的充要条件为 \(\gcd(a,m)=1\)。
模数 \(m\) 为质数时可用费马小定理求逆元。费马小定理：若 \(p\) 是质数且 \(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv1\pmod p\)。将这个式子变形一下，得 \(a\times a^{p-2}\equiv1\pmod p\)，由此可得 \(a^{p-2}\) 即为 \(a\) 模 \(p\) 下的乘法逆元。具体实现可用快速幂，代码不放了。
欧拉函数与欧拉定理
欧拉函数：\(\phi(n)\)，表示小于等于 \(n\) 的正整数中与 \(n\) 互质的数的个数。
性质：
- 如果 \(\gcd(x,y)=1\)，则 \(\phi(x\times y)=\phi(x)\times\phi(y)\)。
- 若 \(p\) 是质数，\(k\ge1\)，则 \(\phi(p^k)=p^k-p{k-1}=p^{k-1}(p-1)\)。
通项公式：\(\phi(n)=n\times\prod(1-\dfrac{1}{p_i})\)，其中 \(n=\prod p_i^{k_i}\)，\(p_i\) 为互不相同的质数。证明：
欧拉定理：若 \(\gcd(a,n)=1\)，则 \(a_{\phi(n)}\equiv1\pmod n\)。
扩展欧拉定理：\(a^b\equiv a^{b\bmod\phi(n)+\phi(n)}\pmod n\)。
Day 1 模拟赛
A
题意
给定一个正整数 \(n\)，可以进行若干次操作，每次操作可选择一个两两不同整数 \(z=p^k\)，其中 \(p\) 为质数，\(k\) 为正整数，且 \(z|n\)，操作后 \(n\to\dfrac{n}{z}\)。求最多操作次数。
题解
先分解质因数。然后显然可以对于每个质因数操作，设 \(k\) 为质因数的次数，操作次数就是满足 \(\sum_{i=1}^{x}i\le k\) 的最大正整数 \(x\)，这个值可以直接暴力算。
代码：
#define ll long long
const int _mxn=+5;
ll n;
int main()
{___();cin>>n;int ans=0;for(ll i=2;i*i<=n;i++)//i 要定义成 long long，不然取模时类型转换会 T，场上因此挂成了 76{int cnt=0;while(n%i==0)//求当前质因数次数{n/=i;cnt++;}int x=1;while(cnt>=x)//求出 x{ans++;cnt-=x;x++;}}if(n>1)//可能没分完剩一个ans++;cout<<ans<<endl;return 0;
}
B
题意
给定整数 \(a,b,c\)，有一个坐标 \((x,y)\) 满足 \(ax+by+c=0\) 且 \(x,y\) 为正整数，\(-5\times10^{18}\le x,y\le5\times10^{18}\)，求出任意一个满足条件的坐标，没有输出 \(-1\)。
题解
exgcd 板子。方程变形一下得 \(ax+by=-c\)，所以只要 \(\gcd(a,b)|c\) 就有解，否则无解。exgcd 求一下然后 \(\times\dfrac{-c}{\gcd(a,b)}\) 即可。这个范围非常大，不用判断。
代码：
#define ll long long
const int _mxn=+5;
ll a,b,c;
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(b==0){x=1,y=0;return a;}ll xx,yy;ll g=exgcd(b,a%b,xx,yy);x=yy;y=xx-a/b*yy;return g;
}
int main()
{___();cin>>a>>b>>c;ll x,y;ll g=exgcd(a,b,x,y);if(c%g==0){cout<<-c/g*x<<" "<<-c/g*y<<endl;}elsecout<<-1<<endl;return 0;
}
C
题意
给定 \(a,b,n,l,r\)，求是否存在整数 \(k\) 满足 \(l\le k\le r\) 且存在非负整数 \(m\) 使 \(n−m\times b=k\times a\)。