Codeforces1182F Maximum Sine (类欧几里得)

本文主要是介绍Codeforces1182F Maximum Sine (类欧几里得)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

#include<bits/stdc++.h>
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<<n<<" "<<a<<" "<<b<<" "<<c<<endl;if(n==-1)return 0;if(a==0)return 1ll*(b/c)*(n+1);if(a>=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<<m<<" "<<c<<" "<<c-b-1<<" "<<a<<"fdsafsdfsa"<<endl;return 1ll*n*(m+1)-gcd(m,c,c-b-1,a);
}
ll sum(int x,int y,int a,int b,int c)
{return gcd(y,a,b,c)-gcd(x-1,a,b,c);
}
bool check(int l,int r)
{return sum(a,b,p,q-l,q)-sum(a,b,p,q-r-1,q)>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<<x<<" "<<y<<endl;x *= t, y *= t;x += 1ll * (a - x) / q * q;while(x < a) x += q;while(x - q >= 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<r-1){int mid=l+r>>1;//cout<<mid<<endl;if(check(q/2-mid,q/2+mid))r=mid;else l=mid;}//cout<<"gfdgdsf"<<endl;long long ans;if(check(q/2-l,q/2+l))ans=l;else ans=r;printf("%lld\n",min(sol(p,q,a,b,q/2-ans),sol(p,q,a,b,q/2+ans)));
}
int main()
{scanf("%d",&t);while(t--){solve();}return 0;
}