[类欧几里得] Maximum Sine_html-js-css

概述题目描述给定整数a,b,p,q，设f(x)=abs(sin(p/q*πx)) 找到最小的可能的整数x使f(x)最大且 a<=x<=b 题解 https://www.cnblogs.com/gczdajuruo/p/11008123.html https://www.luogu.org/problemnew/solution/P5170 1 #include<bits/stdc+

题目描述

给定整数a,b,p,q，设f(x)=abs(sin(p/q*πx))

找到最小的可能的整数x使f(x)最大且 a<=x<=b

题解

https://www.cnblogs.com/gczdajuruo/p/11008123.html

https://www.luogu.org/problemnew/solution/P5170

@H_419_38@ 1 #include<bits/stdc++.h>@H_419_38@ 2 using namespace std;@H_419_38@ 3 typedef long long ll;@H_419_38@ 4 @H_419_38@ 5 ll f(ll n,ll a,ll b,ll c)@H_419_38@ 6  {if(n<0) return 0;@H_419_38@ 7   if(!n)  return b/c;@H_419_38@ 8   if(a>=c || b>=c) return f(n,a%c,b%c,c)+n*(n+1)/2*(a/c)+(n+1)*(b/c);@H_419_38@ 9   ll m=(a*n+b)/c;@H_419_38@10   return m*n-f(m-1,c,c-b-1,a);@H_419_38@11  }@H_419_38@12 @H_419_38@13 inline ll solve(ll l,ll r,ll c)@H_419_38@14  {return f(r,a,c)-f(l-1,c);}@H_419_38@15 @H_419_38@16 voID exgcd(ll a,ll &x,ll &y)@H_419_38@17  {if(!b) {x=1,y=0; return;}@H_419_38@18       @H_419_38@19   exgcd(b,a%b,y,x); y-=a/b*x;@H_419_38@20  } @H_419_38@21  @H_419_38@22 ll a,q;@H_419_38@23 inline ll get(ll p,ll q,ll t)@H_419_38@24  {ll gg=__gcd(p,q);@H_419_38@25   if(t%gg!=0) return 1e18;@H_419_38@26      @H_419_38@27   p/=gg; q/=gg; t/=gg;@H_419_38@28   @H_419_38@29   ll x,y;@H_419_38@30   exgcd(p,q,x,y);@H_419_38@31   @H_419_38@32   x*=t; y*=t;@H_419_38@33   @H_419_38@34   ll k=(a-x)/q; @H_419_38@35   x+=k*q;@H_419_38@36   while(x>=a)x-=q;@H_419_38@37   while(x<a) x+=q;@H_419_38@38   return x;     @H_419_38@39  } @H_419_38@40 inline int red() {@H_419_38@41   int x=0,o=1; char ch = getchar();@H_419_38@42   while((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();@H_419_38@43   if(ch==‘-‘)   o=-1,ch=getchar();@H_419_38@44   @H_419_38@45   while(ch>=‘0‘&& ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();@H_419_38@46   return x*o;@H_419_38@47 } @H_419_38@48 int main()@H_419_38@49  {@H_419_38@50  int t=red(); @H_419_38@51      @H_419_38@52  while(t--)    @H_419_38@53  {a=red();b=red();p=red();q=red();@H_419_38@54   P*=2; q*=2; @H_419_38@55   ll l=0,w=q/2,r=w;    @H_419_38@56   while(l<r)@H_419_38@57    {ll mID=(l+r)>>1;@H_419_38@58        ll L=w-mID,R=w+mID;@H_419_38@59        if(solve(a,q-L,q)-solve(a,q-R-1,q)) r=mID;@H_419_38@60        else                                        l=mID+1;@H_419_38@61    }    @H_419_38@62   printf("%lld\n",min(get(p,w-l),get(p,w+l)));    @H_419_38@63  }    @H_419_38@64 return 0;@H_419_38@65  }