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\)。