数论专题
传送门
https://codeforces.ml/problemset?order=BY_RATING_ASC&tags=math%2Cnumber+theory%2C1800-3000
D. Dima and Lisa
哥德巴赫猜想习题
判断奇数$n$是否能分解为至多$3$个素数之和。
1个素数的情况：本身为质数，$\sqrt{n}$特判。
2个素数的情况：奇=奇+偶，显然只需特判$2,n-2$是否为质数即可。
3个素数的情况：根据弱哥德巴赫猜想：大于$7$的奇数可分解为$3$个质数之和。
我们就先找到小于$n$的最大质数，然后减去它，这样$n$就很小且$n$为偶数。
根据强哥德巴赫猜想：大于$2$的偶数可分解两个质数之和。然后暴力找就可以了。
bool ck(int n){
int mx=sqrt(n);
for(int i=2;i<=mx;i++)
if(n%i==0) return false;
return true;
}
int main(){
int n;
scanf("%d",&n);
if(ck(n)) return printf("1\n%d\n",n),0;
if(ck(n-2)) return printf("2\n2 %d\n",n-2),0;
for(int i=n-2;i>=2;i-=2){
if(ck(i)){
int x=n-i;
for(int j=x-2;j>1;j--)
if(ck(j)&&ck(x-j)){
printf("3\n%d %d %d\n",i,j,x-j);return 0;
}
}
}
return 0;
}D. Same GCDs
$gcd$和欧拉函数定义。
$gcd(a,m)=g=gcd(gk_1,gk_2)=g$
$gcd(k_1,k_2)=1$
$gcd(a+x,m)=gcd((a+x)\pmod{m},m)=g$
$x’=(a+x)\bmod m \in[0,m-1]$
$gcd(a+x,m)=gcd(x’,m)=g$
$x’=x’’g,m=m’g$
$gcd(x’’,m’)=1$
$0\le x’<m\Rightarrow 0\le x’’<m’$
即：$ans=\varphi(m’)$
$\sqrt{n}$求$\varphi(m’)$即可。
ll phi(ll m){
ll s=m;
for(ll i=2;i*i<=m;i++)
if(m%i==0){
s-=s/i;
while(m%i==0) m/=i;
}
if(m>1) s-=s/m;
return s;
}
scanf("%d",&t);while(t--){
scanf("%lld%lld",&a,&m);
ll g=__gcd(a,m);m/=g;
printf("%lld\n",phi(m));
}C. Neko does Maths
$lcm(a+k,b+k)$ 最小，且$k$尽可能小。
令$g=gcd(a+k,b+k)$
令$ans=lcm(a+k,b+k)=\dfrac{(a+k)(b+k)}{g}$
$g=gcd(b-a,a+k)$
枚举$g|(b-a)$，只用在$(b-a)$的因子枚举，然后找到满足$g|(a+k)$的最小$k$，每次比较$lcm$，更新答案$k$。
复杂度：$O(\sqrt{b-a})$
ll a,b;
ll ans=1e18,k,d;
void f(ll x){
ll y=(a+x-1)/x*x;
ll lcm=y/x*(y+d);
if(lcm<=ans) ans=lcm,k=y-a;
}
int main(){
scanf("%lld%lld",&a,&b);
if(a>b) swap(a,b); d=b-a;
for(ll i=1;i*i<=d;i++)
if(d%i==0) f(i),f(d/i);
printf("%lld\n",k);
return 0;
}1225D. Power Products
$\large ab=x^k,k\ge 2$
$\large a=x^{p_1},b=x^{p_2},p_1+p_2=k,(p_1,p_2\ge 0)$
对其进行质因数分解，并对指数$\pmod{k}$，则只需寻找质因数指数之和为$k$的数即可，这样我们可以用一个数组储存当前出现过的数，每次需要的数个数就是答案。
$a=p_1^{k_1}p_2^{k_2}\dots p_m^{k_m},b=p_1^{g_1}p_2^{g_2}\dots p_m^{g_m}$
则$k_i+g_i=k$
int n,k;
int a[N];
ll now,need;
ll ans;
void f(int x,int c){
c%=k;
int u=c,v=(k-c)%k;
while(now&&u--){
now*=x;
if(now>N) now=0;
}
while(need&&v--){
need*=x;
if(need>N) need=0;
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
now=need=1;
int x;scanf("%d",&x);
int mx=sqrt(x);
for(int i=2;i<=mx;i++)
if(x%i==0){
int c=0;
while(x%i==0) c++,x/=i;
f(i,c);
}
if(x>1) f(x,1);
ans+=a[need];
a[now]++;
}
printf("%lld\n",ans);
return 0;
}时间复杂度：$O(n\sqrt{n})$
A. Nezzar and Board
裴蜀定理
https://harris.blog.csdn.net/article/details/113389644
B. Remainders Game
$x_1\equiv x_2\bmod c_i$
则$x_1-x_2\equiv 0\bmod {c_i}$
则$lcm(c_1,c_2\dots,c_n) | (x_1-x_2)$
而$(x_1-x_2)\pmod {k}\ne 0$
所以$lcm(c_1,c_2\dots,c_n)\pmod{k}\ne 0$
同时也是充要条件，构造$x=lcm(c_2,c_2\dots,c_n),y=2lcm(c_1,c_2\dots,c_n)$
为了防止$lcm$爆$long \ long$，可以一边$lcm$一边和$k$取$gcd$。最后看答案是否为$k$即可。
或者线筛一波，找到每个数的最大质因数，预处理出$lcm$的质因数分解。然后判断减掉$k$的所有质因数后是否还有多余的质因数。
ll gcd(ll a,ll b){
return !b?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
int main(){
int n,k;scanf("%d%d",&n,&k);
ll s=1;
for(int i=1;i<=n;i++){
ll x;scanf("%lld",&x);
s=gcd(k,lcm(s,x));
}
puts(s==k?"Yes":"No");
return 0;
}894B. Ralph And His Magic Field
当$n,m$奇偶性不同且$k=-1$无解，因为所有数的乘积按照行和列分别算是不同的。
否则，考虑填完前$n-1$行和前$m-1$列，一共有：$2^{(m-1)(n-1)}$种方案。
最后一行和最后一列是确定的。
ll ksm(ll a,ll n,ll m=mod){
ll s=1;
while(n){
if(n&1) s=s*a%m;
a=a*a%m;
n>>=1;
}
return s;
}
ll n,m,k;
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
if(((n+m)&1)&&k==-1) puts("0");
else printf("%lld\n",ksm(ksm(2,n-1),m-1));
return 0;
}B1. Send Boxes to Alice (Easy Version)
枚举$k$ ，必然是$cnt_1$的因数较小的部分，然后分段模拟，每取移到一段的终点是最优的，最后取最小值即可。
code
vector<int>v;
ll ans=2e18;
void f(int x){
ll s=0;
int mx=SZ(v);
for(int i=0;i<mx;i+=x){
int p=v[(i+i+x-1)/2];
for(int j=i;j<i+x;j++)
s+=abs(p-v[j]);
}
ans=min(ans,s);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
if(x) v.pb(i);
}
sz=SZ(v);
if(sz==1) return puts("-1"),0;
for(int i=2;i*i<=sz;i++)
if(sz%i==0){
f(i);
while(sz%i==0) sz/=i;
}
if(sz>1) f(sz);
printf("%lld\n",ans);
return 0;
}C. Line
$ax+by+c=0$，求$x,y$整数解。这不扩欧$sb$题吗。一开始居然没看出来
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b) {x=1,y=0;return;}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main(){
scanf("%lld%lld%lld",&a,&b,&c);
c=-c;
ll g=__gcd(a,b);
if(c%g) return puts("-1"),0;
ll t=c/g;
ll x,y;
exgcd(a,b,x,y);
x*=t,y*=t;
ll b1=b/g*t,a1=a/g*t;
while(x<-5e18&&b1>0){ //这一步还可以优化
x+=b1;
y-=a1;
}
if(x<-5e18||y>5e18) return puts("-1"),0;
printf("%lld %lld\n",x,y);
return 0;
}963A. Alternating Sum
给了前$k$项，发现递推关系是$\large A_i=A_{i-k}(\dfrac{b}{a})^k$
$\large A_i=s_ia^{n-i}b^i,A_{i-k}=s_{i-k}a^{n-i+k}b^{i-k}$
$\large A_i=A_{i-k}(\dfrac{b}{a})^k$
显然可预处理$[A_0,A_{k-1}]$和他们的和。
$s=\sum\limits_{0}^{k-1} A_i$
$\sum\limits_{i=k}^{2k-1}=s\times (\dfrac{b}{a})^k$
是一个等比数列，令$q=(\dfrac{b}{a})^k$。
$cnt=\dfrac{n+1}{k}$
$sum=\dfrac{s(1-q^{cnt})}{1-q}$
余项暴力求。$q=1$ 需特判，因为此时分母为$0$了。
int main(){
scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
ll inv=ksm(a,mod-2);
ll q=ksm(b*inv%mod,k);
scanf("%s",s);
ll sum=0;
for(int i=0;i<k;i++){
if(s[i]=='+'){
sum=(sum+ksm(a,n-i)*ksm(b,i)%mod)%mod;
}
else {
sum=(sum-ksm(a,n-i)*ksm(b,i)%mod)%mod;
}
}
sum=sum<mod?sum+mod:sum;
ll cnt=(n+1)/k;
ll tot;
if(q==1){
tot=sum*cnt%mod;
}
else tot=sum*(1-ksm(q,cnt))%mod*ksm(1-q,mod-2)%mod;
ll rest=(n+1)%k;
for(int i=n-rest+1;i<=n;i++){
int j=i%k;
if(s[j]=='+'){
tot=(tot+ksm(a,n-i)*ksm(b,i)%mod)%mod;
}
else tot=(tot-ksm(a,n-i)*ksm(b,i)%mod)%mod;
}
printf("%lld\n",tot);
return 0;
}359C. Prime Number
$p$为质数，答案为$p^k$
对每个分子$v_i=sum-a_i$排序，从大到小，然后每次从后往前把相同的小的取出来，看个数是否$\pmod {x}=0$，如果不满足答案就是$p^{w}$。
否则合并一下，丢$\dfrac{cnt}{x}$个 $w+1$进去。
for(int i=1;i<=n;i++)
v.pb(sum-a[i]);
sort(v.rbegin(),v.rend());
while(1){
ll w=v.back();
ll cnt=0;
while(!v.empty()&&v.back()==w){
cnt++;v.pop_back();
}
if(cnt%x){
w=min(w,sum);
printf("%lld\n",ksm(x,w));
return 0;
}
else {
cnt/=x;
for(int i=0;i<cnt;i++)
v.pb(w+1);
}
}
