2527

yxc

hlydxxz

Cold_heartless
EWliao

ease

hongk_bb
Fcy
wanghai673
S搁浅S

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

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}

int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
LL n, d, x, y, a, b;
scanf("%lld%lld%lld%lld", &n, &d, &x, &y);

int gcd = exgcd(n, d, a, b);
if ((y - x) % gcd) puts("Impossible");
else
{
b *= (y - x) / gcd;
n /= gcd;
printf("%lld\n", (b % n + n) % n);
}
}

return 0;
}


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

using namespace std;

int exgcd(int a,int b,int &x, int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);

y-=a/b*x;
return d;
}

int main()
{
int n;
scanf("%d", &n);
while(n--)
{
int a,b,x,y;
scanf("%d%d",&a,&b);

exgcd(a,b,x,y);

printf("%d %d\n",x,y);
}
return 0;

}



#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1e5+10;

int a[N];
int n;

int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++)    scanf("%d", &a[i]);
sort(a,a+n);

int ans=0;
for(int i=0;i<n-1;i++)  ans=__gcd(ans,a[i+1]-a[i]);

if(ans != 0 )
cout<<(a[n-1]-a[0]) / ans + 1<<endl;
else
cout<<n<<endl;

return 0;
}


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

using namespace std;

typedef long long LL;

const int N = 3e5+10;

int n;
LL a[N],s[N];
bool st[N];

int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
s[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%lld", &a[i]);
s[i] = s[i-1]+a[i];
}

LL s0=s[0],sn=s[n];
if(s0 > sn) swap(s0,sn);
sort(s,s+n+1);

for(int i=0;i<=n;i++)
if(s[i]==s0)
{
s0=i;
break;
}
for(int i=n;i>=0;i--)
if(s[i]==sn)
{
sn=i;
break;
}

memset(st, 0, sizeof st);
int l = 0, r = n;
for (int i = s0; i >= 0; i -= 2)
{
a[l ++ ] = s[i];
st[i] = true;
}
for (int i = sn; i <= n; i += 2)
{
a[r -- ] = s[i];
st[i] = true;
}
for(int i=0;i<=n;i++)
if(!st[i])
a[l++]=s[i];

LL res=0;
for(int i=1;i<=n;i++)   res=max(res,abs(a[i]-a[i-1]));

printf("%lld\n",res);
}

return 0;
}


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

using namespace std;

typedef long long LL;

const int N = 200010;

int n, m;
int a[N];

int main()
{
scanf("%d%d", &n, &m);
int k = n + m + 1;
for (int i = 0; i < k; i ++ ) scanf("%d", &a[i]);

LL res = 0;
if (!m)
{
for (int i = 0; i < k; i ++ ) res += a[i];
}
else
{
sort(a, a + k);  // 也可以不排序，找出最大值和最小值即可

res = a[k - 1] - a[0];
for (int i = 1; i < k - 1; i ++ ) res += abs(a[i]);
}

printf("%lld\n", res);

return 0;
}



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

using namespace std;

typedef long long LL;

const int N = 1e5+10,MOD=1000000009;

int a[N];
int n,k;

int main()
{
scanf("%d%d", &n,&k);
for(int i=0;i<n;i++)    scanf("%d", &a[i]);
sort(a,a+n);

int res=1,sign=1;
int l=0,r=n-1;
if(k%2)
{
res=a[r--];
k--;
if(res<0)   sign=-1;
}

while(k)
{
LL x = (LL)a[l]*a[l+1],y=(LL)a[r-1]*a[r];
if(x * sign > y * sign)
{
res=x % MOD * res % MOD;
l+=2;
}
else
{
res=y % MOD * res % MOD;
r-=2;
}
k-=2;
}
printf("%d\n",res);

return 0;
}


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 5e5+10;

int n;
int a[N];
long double res,s;

int main()
{
cin>>n>>s;
for(int i=0;i<n;i++)
scanf("%d", &a[i]);

sort(a,a+n);

long double avg=s/n;
for(int i=0;i<n;i++)
{
double cur=s/(n-i);
if(a[i] < cur)//如果小于平均数就让他取自身
cur=a[i];
res+=(cur-avg)*(cur-avg);
s-=cur;
}
res/=n;
printf("%.4Lf\n",sqrt(res));

return 0;

}


#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1e3+10;

int n,d;
struct Segment
{
double l,r;
bool operator<(Segment&t)   const
{
return r<t.r;
}
}seg[N];

int main()
{
scanf("%d%d", &n, &d);
bool failed = false;
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(y>d) failed = true;
else
{
double len = sqrt(d*d-y*y);
seg[i].l = x-len, seg[i].r=x+len;
}
}
if(failed)
puts("-1");
else
{
sort(seg,seg+n);

int cnt=0;
double last=-1e20;
for(int i=0;i<n;i++)
{
if(last<seg[i].l)
{
cnt++;
last=seg[i].r;
}
}
printf("%d\n",cnt);
}

return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6+10;

typedef long long LL;

int a[N];
int n;
LL c[N];

int main()
{
scanf("%d", &n);

LL sum=0;
for(int i=1;i<=n;i++)    scanf("%d", &a[i]),sum+=a[i];

LL avg = sum/n;
for(int i=n;i>1;i--)
c[i]=c[i+1]+avg-a[i];
c[1]=0;

sort(c+1,c+n+1);

LL res=0;
LL mid=c[(n+1)/2];
for(int i=1;i<=n;i++)   res+=abs(c[i]-mid);

printf("%lld\n",res);

return 0;

}


#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int a[N];
int n;

int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++)    scanf("%d",&a[i]);
sort(a,a+n);

LL ans;
int c=a[n/2];

for(int i=0;i<n;i++)    ans+=abs(a[i]-c);

printf("%lld\n",ans);

return 0;

}