锐客网

  1. 首页 > it技术 > >

cf|Codeforces1182F Maximum Sine (类欧几里得)

cf

【cf|Codeforces1182F Maximum Sine (类欧几里得)】传送门
f ( x ) = abs ( sin ( p q π x ) ) f(x) = \text{abs}(\text{sin}(\frac{p}{q} \pi x)) f(x)=abs(sin(qp?πx))
求整数x在[a,b]之间 f x f_x fx?最大值
这道题官方给的题解是分块暴力？参考qzh巨佬题解，我也用类欧几里得做的这道题
首先sin非常不友善，我们发现这题可以转化为求 p x q \frac{px}{q} qpx?最接近 k + 1 2 k+\frac {1}{2} k+21?的 x x x
即 p ? xm o dq p\cdot x \ mod \ q p?x mod q 最接近q 2 \frac{q}{2} 2q?
同时乘2，得 2 p ? xm o d2 q 2p\cdot x \ mod \ 2q 2p?x mod 2q 最接近q q q
考虑转化为可行性问题，二分mid,则问题转化为是否存在x使得 2 p ? xm o d2 q 2p\cdot x \ mod \ 2q 2p?x mod 2q在 [ q ? m i d , q + m i d ] [q-mid,q+mid] [q?mid,q+mid]上有取值
问题等价于求 ∑ x = a b ? p x ? l q ? ? ? p x ? r ? 1 q ? \sum_{x=a}^b\lfloor\frac{px-l}{q}\rfloor - \lfloor\frac{px-r-1}{q}\rfloor ∑x=ab??qpx?l????qpx?r?1??是否大于0其中 l = q ? m i d , r = q + m i d l=q-mid,r=q+mid l=q?mid,r=q+mid
这个意思就是说看你这段里跨没跨过一个q的整数倍，如果跨过了那么这两个值就会不同
用类欧几里得 f x f_x fx?求解即可
最后用exgcd还原x
Code

#include using namespace std; typedef long long ll; int t; int a,b,p,q; ll gcd(int n,int a,int b,int c) { //cout<=c||b>=c) { return 1ll*n*(n+1)/2*(a/c)+1ll*(n+1)*(b/c)+gcd(n,a%c,b%c,c); } ll m=(1ll*a*n+b)/c-1; //cout<0?1:0; } void exgcd(int a,int b,ll &x,ll &y) { if(b==0) { x=1; y=0; return ; } exgcd(b,a%b,y,x); y-=a/b*x; } ll sol(int p,int q,int a,int b,int t) { int gc=__gcd(p,q); if(t%gc)return 1e18; p /= gc, q /= gc, t /= gc; ll x, y; exgcd(p, q, x, y); //cout<= a) x -= q; if(x > b) return 1e18; return x; } void solve() { scanf("%d%d%d%d",&a,&b,&p,&q); p*=2,q*=2; int l=0,r=q/2; while(l>1; //cout<

    推荐阅读


    上一篇：囚狐|囚狐 42 / 丑态

    下一篇：gdb及其core调试