CF710D题解

· · 题解

不会 excrt 的朋友请先去你谷的板子题或者 OIwiki 学一下。

坑巨多无比。

首先对于 a_1,b_1,a_2,b_2 可以上 excrt 先求出最小整数解，然后得出最在 [L,R] 范围内的最小和最大解（公差为 \operatorname{lcm}(a_1,a_2)）,最后利用等差数列算项数即可。

然后 WA on #3

数据：

2 0 4 2 -39 -37

这个时候我回去读了一遍英文题面，发现原来这个 x 不能小于 \max(b_1,b_2) （就是 k',l'>=0 这一句，顺带一提，b_1,b_2 要提前存起来，不然的话原来的值在 excrt 里会被更改）

然后我的输出部分从

cout<<(r-l)/lcm+1;

变成了

l=max(l,max(b1,b2));
if(l>r)cout<<0;
else cout<<(r-l)/lcm+1;

然后激情 WA on #28 （

数据：

2 0 2 1 0 1000000000

我寻思着这不无解吗，然后我跑回去一看我的 excrt 函数返回 -1 的时候我应该直接输出 0 然后 return 但是我没有（

然后再交了一遍，终于过了（）

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],b[100005];
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y),x0=x,y0=y;
    x=y0;
    y=x0-a/b*y0;
    return d;
}
int inv(int x,int p){
    int x0,y0;
    exgcd(x,p,x0,y0);
    return x0;
}
int excrt(){
    int lcm=a[1];
    int ans=b[1];
    for(int i=2;i<=n;++i){
        b[i]=((b[i]-ans)%a[i]+a[i])%a[i];
        int x0,y0;
        int d=exgcd(lcm,a[i],x0,y0);
        if(b[i]%d)return -1;
        int k=(a[i]+b[i]/d*x0%a[i])%a[i];
        ans=ans+k*lcm;
        lcm=lcm/d*a[i];
        ans=(ans+lcm)%lcm;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    n=2;    
    int b1,b2;//提前存一下
    for(int i=1;i<=2;++i){
        cin>>a[i]>>b[i];
        if(i==1)b1=b[1];
        else b2=b[2];
        b[i]=(b[i]%a[i]+a[i])%a[i];
    }
    int lt,rt;
    cin>>lt>>rt;
    int cur=excrt(),lcm=a[1]/__gcd(a[1],a[2])*a[2];
    if(cur==-1){//无解
        cout<<0;
        return 0;
    }
    int l=(lt-cur)/lcm*lcm+cur;
    if(l<lt)l+=lcm;//首项
    int r=(rt-cur)/lcm*lcm+cur;
    if(r>rt)r-=lcm;//末项
//  cout<<l<<' '<<r<<'\n';
    l=max(l,max(b1,b2));
    if(l>r)cout<<0;
    else cout<<(r-l)/lcm+1;
    return 0;
}