#include<iostream>
#include<algorithm>
using namespace std;
const int N=50010;
int primes[N],cnt;
bool used[N];
int ans[N],len;
void get_primes(int n){//线性筛素数（欧拉筛法）
    for(int i=2;i<=n;i++){
        if(!used[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            used[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}
bool is_prime(int x){
    if(x<N) return !used[x];//小于N的数已经被筛选了，所以只需要返回used[x]即可
    for(int i=2;i<=x/i;i++)
        if(x%i==0) return false;
    return true;
}
//素数表primes[]中上一个素数的下标，prod是各个质因子最高次幂的乘积，s为约数和
void dfs(int last,int prod,int s){
    if(s==1){
        ans[len++]=prod;
        return ;
    }
    //保证当前质数大于上一个质数，可以保证不会出现重复解
    if(s-1>(last <0?1:primes[last])&&is_prime(s-1))
        ans[len++]=prod*(s-1);
    //1.下面的循环只会枚举导sqrt(s)，所以不会重复
    //2.即使s-1是质数也可能是次幂和的形式，不能return返回
    for(int i=last+1;primes[i]<=s/primes[i];i++){
        int p=primes[i];
        for(int j=p+1,t=p;j<=s;t*=p,j+=t){
            if(s%j==0)
                dfs(i,prod*t,s/j);
        }
    }
}
int main(){
    int s;
    get_primes(N);
    while(cin>>s){
        len=0;
        dfs(-1,1,s);
        cout<<len<<endl;
        if(len){
            sort(ans,ans+len);
            for(int i=0;i<len;i++) 
                cout<<ans[i]<<' ';
            cout<<endl;
        }
    }
    return 0;
}

map做法

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int main(){
    map<int,int> b;//相当于差分数组
    int n,x=0;
    char s[2];
    cin>>n;
    while(n--){
        int y;
        cin>>y>>s;
        if(*s=='R'){
             b[x]++;
             b[x+y]--;
             x+=y;
        }
        else {
            b[x-y]++;
            b[x]--;
            x-=y;
        }
    }
    int sum=0,ans=0,last;
    for(auto [x,v] : b){//根据差分数组来计算被涂了至少两层的栅栏
        if(sum>=2) ans+=x-last;
        last=x;
        sum+=v;
    }
    cout<<ans<<endl;
    return 0;
}

离散化做法

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=200010;
typedef pair<int,int> PII;
vector<PII> segs;
vector<int> alls;//所有的端点
int sum[N];
int find(int x){//二分查找
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l+1;
}
int main(){
    int n,x=0;
    cin>>n;
    char s[2];
    while(n--){
        int y;
        cin>>y>>s;
        if(*s=='R'){
            segs.push_back({x,x+y});
            alls.push_back(x),alls.push_back(x+y);
            x+=y;
        }
        else{
            segs.push_back({x-y,x});
            alls.push_back(x),alls.push_back(x-y);
            x-=y;
        }
    }
    sort(alls.begin(),alls.end());//排序
    alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重
    for(auto [l,r] : segs){//对差分数组进行操作
        l=find(l);
        r=find(r);
        sum[l]++;
        sum[r]--;
    }
    int ans=0;
    for(int i=1;i<=alls.size();i++){//计算前缀和
        sum[i]+=sum[i-1];
        if(sum[i]>=2) ans+=alls[i]-alls[i-1];
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5010;
int primes[N],cnt;
bool st[N];
int sum[N];
void get_primes(int n){//线性筛法
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}
int get(int n,int p){//求n！中质因子p出现的次数 时间复杂度:logn
    int ans=0;
    while(n){
        ans+=n/p;
        n/=p;
    }
    return ans;
}
vector<int> mul(vector<int> a,int b){//高精度乘法
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size();i++){
        t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    while(t){//处理最后的进位
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
int main(){
    int a,b;
    cin>>a>>b;
    get_primes(5000);
    for(int i=0;i<cnt;i++){
        int p=primes[i];
        sum[i]=get(a,p)-get(a-b,p)-get(b,p);
    }
    vector<int> res;
    res.push_back(1);
    for(int i=0;i<cnt;i++)
        for(int j=0;j<sum[i];j++)
            res=mul(res,primes[i]);
    for(int i=res.size()-1;i>=0;i--) cout<<res[i];
    cout<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int M=20;
typedef long long ll;
int n,m;
int p[M];
int main(){
    int n,m,res=0;
    cin>>n>>m;
    for(int i=0;i<m;i++)  cin>>p[i];
    for(int i=1;i<1<<m;i++){//枚举每种选择
        int s=0;
        int t=1;
        for(int j=0;j<m;j++){//遍历每种选择中哪些集合被选中
            if(i>>j&1){
                if((ll)t*p[j]>n){//一旦多个质数的乘积大于n，那么对于结果就没有贡献
                    t=-1;
                    break;
                }
                s++;
                t*=p[j];
            }
        }
        if(t==-1) continue;
        if(s&1) res+=n/t;//集合选择的个数为奇数，符号位+
        else res-=n/t;//集合的选择个数为偶数，符号位-
    }
    cout<<res<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){//使用扩展欧几里得计算出k1'
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;//返回的d可能为负数
}
int main(){
    ll x=0,a1,m1,n;//x用来存储新得到的等式的余数
    cin>>n;
    cin>>m1>>a1;
    for(int i=0;i<n-1;i++){
        ll a2,m2;
        cin>>m2>>a2;
        ll k1,k2;
        ll d=exgcd(m1,m2,k1,k2);
        if((a2-a1)%d){
            x=-1;
            break;
        }
        k1*=(a2-a1)/d;  //k1=k1'*(a2-a1)/d
        // k1=k1+k(m2/d);
        ll t=m2/d;     
        k1=(k1%t+t)%t;//保证k1为最小的正整数，在计算的过程中不会溢出

        a1=x=k1*m1+a1;//计算新的余数 a1=k1*m1+a1

        m1=abs(m2/d*m1);//计算新的取模的数  m1=k*lcm(m1,m2)

    }
    if(x!=-1) x=(a1%m1+m1)%m1;//最后一个等式: x=a0 mod m0
    cout<<x<<endl;
    return 0;
}

暴力大法（2076ms）

时间复杂度：$(n^3)$
算法思想：先固定前两个点$k，i$，然后第三个点$j$一直向后遍历，每次遍历到一个新的位置，判断第三个点的位置是否满足$a[i]-a[k]<=a[j]<=2*(a[i]-a[k])+a[i]$ ,如果满足条件，结果res++。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
typedef long long ll;
ll a[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    /*for(int i=0;i<n;i++) cout<<a[i]<<' ';
    cout<<endl;*/
    int res=0;
    for(int k=0;k<n;k++){
        for(int i=k+1;i<n;i++){
            for(int j=i+1;j<n;j++){
                ll x=a[i]-a[k];
                if(a[j]>=a[i]+x&&a[j]<=a[i]+2*x) res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

二分打法(245ms)

时间复杂度：$O(n^2\cdot log_2^n)$
主要在第三层循环进行优化，假设前两个点的坐标分别为a[k],a[j]，那么距离$x=a[i]-a[k]$。 第三个点的坐标范围应该在$[x+a[i],2x+a[i]]$之间，使用二分进行查找第一个大于或等于$x+a[i]$的数在数组中的下标$l$，在使用二分查找第一个小于或等于$2x+a[i]$的数在数组中的下标$r$，结果$res=r-l+1$。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
typedef long long ll;
ll a[N];
int left_bound(int l,int r,ll x){
    while(l<r){
        int mid=l+r>>1;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    if(a[l]>=x) return l;
    return -1;//返回-1是为了区别没找到数和刚好数组最后一个数满足条件的情况，下同
}
int right_bound(int l,int r,ll x){
    while(l<r){
        int mid=l+r+1>>1;
        if(a[mid]<=x) l=mid;
        else r=mid-1;
    }
    if(a[l]<=x) return l;
     return -1;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);

    int res=0;
    for(int k=0;k<n;k++){
        for(int i=k+1;i<n;i++){
            int s=a[i]-a[k];
            int l=left_bound(i+1,n-1,s+a[i]);
            int r=right_bound(i+1,n-1,s*2+a[i]);
            if(l==-1||r==-1) continue;
            //cout<<l<<' '<<r<<endl;
            res+=r-l+1;
        }
    }
    cout<<res<<endl;
    return 0;
}

暴力打法（三重循环）

时间复杂度：$(n^3)$

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
typedef long long ll;
ll a[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    /*for(int i=0;i<n;i++) cout<<a[i]<<' ';
    cout<<endl;*/
    int res=0;
    for(int k=0;k<n;k++){
        for(int i=k+1;i<n;i++){
            for(int j=i+1;j<n;j++){
                ll x=a[i]-a[k];
                if(a[j]>=a[i]+x&&a[j]<=a[i]+2*x) res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

二分打法

时间复杂度：$O(n^2\cdot log_2^n)$

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
typedef long long ll;
ll a[N];
int left_bound(int l,int r,ll x){
    while(l<r){
        int mid=l+r>>1;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    if(a[l]>=x) return l;
    return -1;
}
int right_bound(int l,int r,ll x){
    while(l<r){
        int mid=l+r+1>>1;
        if(a[mid]<=x) l=mid;
        else r=mid-1;
    }
    if(a[l]<=x) return l;
     return -1;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);

    int res=0;
    for(int k=0;k<n;k++){
        for(int i=k+1;i<n;i++){
            int s=a[i]-a[k];
            int l=left_bound(i+1,n-1,s+a[i]);
            int r=right_bound(i+1,n-1,s*2+a[i]);
            if(l==-1||r==-1) continue;
            //cout<<l<<' '<<r<<endl;
            res+=r-l+1;
        }
    }
    cout<<res<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d,x1,y1;
    d=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return d;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b,m;
        cin>>a>>b>>m;
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d) puts("impossible");
        else cout<<(ll) b/d*x%m<<endl;
    }
    return 0;
}

朴素版(286ms)

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll qmi(ll a,ll k,ll p){
    ll res=1;
    while(k){
        if(k&1) res=(ll) res*a%p;
        a=(ll) a*a%p;
        k>>=1;
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    int a=2*n,b=n;
    int res=1;
    for(int i=a;i>a-b;i--) res=(ll) res*i%mod;
    for(int i=1;i<=b;i++) res=(ll) res*qmi(i,mod-2,mod)%mod;
    cout<<(ll) res*qmi(n+1,mod-2,mod)%mod<<endl;
    return 0;
}

优化版(20ms)

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll qmi(ll a,ll k,ll p){
    ll res=1;
    while(k){
        if(k&1) res=(ll) res*a%p;
        a=(ll) a*a%p;
        k>>=1;
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    int a=2*n,b=n;
    ll x=1,y=1;
    for(int i=0;i<b;i++){//优化点
        x=(ll) x*(a-i)%mod;
        y=(ll) y*(i+1)%mod;
    }
    cout<<(ll)x*qmi(y,mod-2,mod)%mod*qmi(n+1,mod-2,mod)%mod<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(ll)res*a%p;
        a=(ll) a*a%p;
        k>>=1;
    }
    return res;
}
int C(int a,int b,int p){
    if(b>a) return 0;
    if(b>a-b) b=a-b;//优化一组合数的对称性:c5取4=c5取1
    ll x=1,y=1;
    for(int i=0;i<b;i++){//优化二
        x=(ll) x*(a-i)%p;
        y=(ll) y*(i+1)%p;
    }
    return x*qmi(y,p-2,p)%p;
}
int lucas(ll a,ll b,int p){
    if(a<p&&b<p) return C(a,b,p);
    return (ll)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int p;
        ll a,b;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}