题解 | #智乃的C语言模除方程#

J题智乃的C语言模除方程

题目改成查询从u到0，有多少个数出现过，分成两部分，一部分是u % p的部分，一部分是每一份为0 ~ p -1(注意分正负考虑)，有 u / p 份。两份加起来就是答案

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll ;
int p,l,r,L,R ;

int get_intersection(int a,int b,int c,int d){ //返回[a,b],与[c,d]交集长度
    if(c > b || d < a) return 0;
    return min(d,b) - max(a,c) + 1 ;
}

int query(int u){  // 可以查询从u到0，有多少个数出现过，分成两部分，一部分是u % p的部分，一部分是有 u / p 份，每一份为0 ~ p -1(注意分正负考虑)
    if(u < 0) return (int)abs(u / p) * get_intersection(-p+1,0,l,r) + get_intersection(u % p,0,l,r) ;
    return (int)(u / p) * get_intersection(0,p-1,l,r) + get_intersection(0,u % p,l,r) ;
}

int main(){
    
    cin >> p >> l >> r >> L >> R ;
    p = abs(p) ;
    
  	int ans = 0 ;  
  	
 	// 类似前缀和思路
    if(L <= 0 && R >= 0) ans = query(L) + query(R) - query(0) ;  // L与R异号，多算一次0，所以删除0
    else if(L < 0 && R < 0) ans = query(L) - query(R+1) ;  // 都小于0
    else ans = query(R) - query(L - 1) ;  // 都大于0

    cout << ans << "\n" ;
    return 0;
}