# CF1182F Maximum Sine

Title Description: find the integer $x\in [a,b]$to make $|$2px \ mod \ 2q-q| $minimum. If there are multiple$x $output minimum. Data range:$1\leq a,b,p,q\leq 10^9$The first question is not a template. First of all, try dichotomy. How to judge$2px \ mod \ 2q \in [l,r] $? We found $$[2px \ mod \ 2q \in [l,r]]=\lfloor\frac{2px-l}{2q}\rfloor-\lfloor\frac{2px-r-1}{2q}\rfloor$$ So there is$x\in [a,b] $to make$2px \ mod \ 2q \in [l,r] $. It is only necessary to judge whether$\ sum {x = a} ^ B (\ lfloor \ frac {2px-l} {2q} \ rfloor - \ lfloor \ frac {2px-r-1} {2q} \ rfloor) $is greater than 0. This is done by eurolike calculation. After finding the minimum deviation value of$l $, we can use the extended Europe to solve the congruence equation. Time complexity$O(\log^2 n) $.  1 #include<bits/stdc++.h> 2 #define Rint register int 3 using namespace std; 4 typedef long long LL; 5 LL t, a, b, p, q, len; 6 inline LL calc(LL a, LL b, LL c, LL n){ 7 if(!a || !n) return (n + 1) * (b / c); 8 if(n < 0) return 0; 9 LL m = (a * n + b) / c; 10 if(a >= c || b >= c) return calc(a % c, b % c, c, n) + (n * (n + 1) >> 1) * (a / c) + (n + 1) * (b / c); 11 return m * n - calc(c, c - b - 1, a, m - 1); 12 } 13 inline LL exgcd(LL a, LL b, LL &x, LL &y){ 14 if(!b){x = 1; y = 0; return a;} 15 LL gcd = exgcd(b, a % b, y, x); 16 y -= a / b * x; 17 return gcd; 18 } 19 int main(){ 20 scanf("%lld", &t); 21 while(t --){ 22 scanf("%lld%lld%lld%lld", &a, &b, &p, &q); 23 LL l = 0, r = q, mid, P = p << 1, Q = q << 1; 24 while(l < r){ 25 mid = l + r >> 1; 26 LL L = q - mid, R = q + mid + 1; 27 if(calc(P, Q - L, Q, b) + calc(P, Q - R, Q, a - 1) - calc(P, Q - L, Q, a - 1) - calc(P, Q - R, Q, b) > 0) r = mid; 28 else l = mid + 1; 29 } 30 LL x, y, gcd = exgcd(P, Q, x, y), ans = 1e9; P /= gcd; Q /= gcd; 31 if((q - l) % gcd == 0){ 32 LL xx = (q - l) / gcd * x; xx += (a - xx) / Q * Q; 33 while(xx >= a) xx -= Q; while(xx < a) xx += Q; 34 ans = min(ans, xx); 35 } 36 if((q + l) % gcd == 0){ 37 LL xx = (q + l) / gcd * x; xx += (a - xx) / Q * Q; 38 while(xx >= a) xx -= Q; while(xx < a) xx += Q; 39 ans = min(ans, xx); 40 } 41 printf("%lld\n", ans); 42 } 43 } CF1182F Later, I saw a wave of official solutions, and found that it was a block like BSGS, with a time complexity of$O(\sqrt{n}) \$. (if you write badly, you need to bring a log...)