Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

## [校内训练20_01_22]ABC

GreenDuck 2020-02-02 17:15:00 阅读数:26 评论数:0 点赞数:0 收藏数:0

1.给出序列A，求序列B，使得bi|ai,lcm(b1,b2,...,bn)=lcm(a1,a2,...,an)且字典序最小。

``` #include <cstdio>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

const int MAXN = ;

LL num[MAXN];
LL common[MAXN];
int n, cs;

LL gcd(LL a, LL b)
{
LL tmp;
while (b) tmp = a, a = b, b = tmp % b;
return a;
}

void solve()
{
for (int i = ; i < n; i++){
cs = ;
for (int j = ; j < n; j++)
if (i != j)
common[cs ++] = gcd(num[i], num[j]);
LL s = ;
for (int j = ; j < cs; j++){
s *= common[j];
for (int k = j+; k < cs; k++)
common[k] /= gcd(common[j], common[k]);
}
num[i] /= s;
while (true){
LL x = gcd(num[i], s);
if (x == )
break;
num[i] *= x;
s /= x;
}
}
}

int main()
{
freopen("transform.in", "r", stdin);
freopen("transform.out", "w", stdout);
scanf("%d", &n);
for (int i = ; i < n; i ++)
scanf("%lld", &num[i]);
solve();
for (int i = ; i < n; i ++)
printf("%lld ", num[i]);
printf("\n");
return ;
}```
View Code

``` #include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
ll n,a[],ans[];
map<ll,ll>cnt,where;
namespace math
{
const int len=;
ll test[len]={,,,,,,,,,};
ll size,wait[];
inline ll mul(ll x,ll y,ll mod)
{
ll d=(ld)x*y/mod;
return ((x*y-d*mod)%mod+mod)%mod;
}
inline ll QPOW(ll x,ll y)
{
ll ans=;
for(int i=;i<=y;++i)
ans=ans*x;
return ans;
}
inline ll qpow(ll x,ll y,ll mod)
{
ll ans=,base=x;
while(y)
{
if(y&)
ans=mul(ans,base,mod);
base=mul(base,base,mod);
y>>=;
}
return ans;
}
inline bool isPrime(ll p)
{
for(int i=;i<len;++i)
{
if(p<test[i])
return false;
else if(p==test[i])
return true;
ll x=qpow(test[i],p-,p),d=p-;
if(x!=)
return false;
while(x==&&d%==)
{
d>>=;
x=qpow(test[i],d,p);
if(x!=&&x!=p-)
return false;
}
}
return true;
}
ll gcd(ll x,ll y)
{
if(y==)
return x;
return x%y==?y:gcd(y,x%y);
}
inline ll f(ll x,int c,ll mod)
{
return (mul(x,x,mod)+c)%mod;
}
inline ll find(ll n,int step,int c)
{
if(n%==)
return ;
ll x=,y=,d=;
while(true)
{
ll tmpX=x,tmpY=y,d=;
for(int i=;i<=step;++i)
{
x=f(x,c,n);
y=f(f(y,c,n),c,n);
d=mul(d,(x%n-y%n+n)%n,n);
}
d=gcd(d,n);
if(d==)
continue;
else if(d!=n)
return d;
x=tmpX,y=tmpY;
for(int i=;i<=step;++i)
{
x=f(x,c,n);
y=f(f(y,c,n),c,n);
d=gcd(n,(x%n-y%n+n)%n);
if(d!=&&d!=n)
return d;
}
return ;
}
return -;
}
void factor(ll x)
{
if(isPrime(x))
{
wait[++size]=x;
return;
}
ll step=pow(x,0.1)+,c=,now=;
while(!now)
now=find(x,step,++c);
factor(now),factor(x/now);
}
void pollard(ll x,int num)
{
size=;
factor(x);
map<ll,ll>G;
// for(int i=1;i<=size;++i)
// cout<<wait[i]<<" ";
// cout<<endl;
for(int i=;i<=size;++i)
++G[wait[i]];
for(int i=;i<=size;++i)
{
x=wait[i];
if(G[x]>=cnt[x])
{
ans[where[x]]/=QPOW(x,cnt[x]);
cnt[x]=G[x];
where[x]=num;
ans[num]*=QPOW(x,cnt[x]);
}
}
}
}
inline bool check(int x)
{
if(x==)
return false;
for(int i=;i*i<=x;++i)
if(x%i==)
return false;
return true;
}
int main()
{
freopen("transform.in","r",stdin);
freopen("transform.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;++i)
{
cin>>a[i];
ans[i]=;
math::pollard(a[i],i);
}
for(int i=;i<=n;++i)
cout<<ans[i]<<" ";
cout<<endl;
return ;
}```
View Code

2.有一些机场和航线，航线是形如点A到点B的直线，飞机会准时从t1出发t2到达，期间匀速直线运动。机场和飞机都配备雷达，雷达有固定范围R，你需要保证在任意时间内，任意在飞行中的飞机能够通过雷达直接或间接地与机场相连，求最小的R。

``` #include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps=1E-;
const ld inf=1E12;
int n,m;
int A[],B[];
ld from[],to[],length[];
struct pt
{
ld x,y;
pt(ld a=,ld b=):x(a),y(b){}
pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
pt operator*(const ld&d){return pt(x*d,y*d);}
pt operator/(const ld&d){return pt(x/d,y/d);}
ld operator*(const pt&A){return x*A.y-y*A.x;}
ld operator&(const pt&A){return x*A.x+y*A.y;}
void out()
{
cout<<"("<<x<<","<<y<<")";
}
}p[];
struct line
{
pt A,B;
line(pt a=pt(),pt b=pt()):A(a),B(b){}
};
struct info
{
ld L,R;
int x,y;
info(ld a=,ld b=,int c=,int d=):L(a),R(b),x(c),y(d){}
}tmp[555555];
inline ld s(ld x){return x*x;}
inline pt intersection(line a,line b)
{
pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
if(abs(A*B)<=eps)
return pt(inf,inf);
ld d=-(B*C)/(B*A);
return b.A+A*d;
}
inline pt T(pt A)
{
return pt(-A.y,A.x);
}
inline pt perpendicular(pt A,line a)
{
if(abs((A-a.A)*(A-a.B))<=eps)
return A;
pt B=A+T(a.B-a.A);
return intersection(line(A,B),a);
}
inline ld dis(pt A,pt B)
{
return sqrt(s(A.x-B.x)+s(A.y-B.y));
}
namespace graph
{
bool vis[];
struct edge
{
int to,next;
}E[555555];
inline void clear()
{
for(int i=;i<=n+m;++i)
for(int i=;i<=size;++i)
E[i].to=E[i].next=;
size=;
}
{
E[++size].to=v;
}
inline bool ok(ld x)
{
for(int i=;i<=n+m;++i)
vis[i]=;
queue<int>Q;
for(int i=;i<=n;++i)
{
Q.push(i);
vis[i]=;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
{
int v=E[i].to;
if(vis[v])
continue;
Q.push(v);
vis[v]=;
}
}
for(int i=n+;i<=n+m;++i)
if((!vis[i])&&(from[i-n]-eps<=x&&x<=to[i-n]+eps))
return false;
return true;
}
}
int tot;
inline bool test(ld x)
{
graph::clear();
for(int i=;i<=tot;++i)
if(tmp[i].L-eps<=x&&x<=tmp[i].R+eps)
{
}
return graph::ok(x);
}
inline bool check(ld r)
{
tot=;
for(int i=;i<=n;++i)
{
pt O=p[i];
for(int j=;j<=m;++j)
{
line a(p[A[j]],p[B[j]]);
pt P=perpendicular(O,a),D,pA,pB;
ld d=s(P.x-O.x)+s(P.y-O.y);
if(d>r*r-eps)
continue;
else if(abs(d)<=eps)
D=(a.B-a.A)*r/dis(a.A,a.B);
else
D=T((P-O)*sqrt(r*r/d-));
pA=P+D,pB=P-D;
ld t1=((pA-p[A[j]])&(p[B[j]]-p[A[j]]))/length[j]/length[j]*(to[j]-from[j])+from[j];
ld t2=((pB-p[A[j]])&(p[B[j]]-p[A[j]]))/length[j]/length[j]*(to[j]-from[j])+from[j];
if(t1>t2)
swap(t1,t2);
t1=max(from[j],t1);
t2=min(to[j],t2);
if(t2-t1>=eps)
tmp[++tot]=info(t1,t2,i,n+j);
}
}
for(int i=;i<=m;++i)
for(int j=;j<=m;++j)
{
if(from[i]<=from[j])
continue;
ld delT=from[i]-from[j];
ld g=(ld)(to[i]-from[i])/(ld)(to[j]-from[j]-delT);
pt I=p[A[i]]-p[B[i]];
pt J=(p[B[j]]-p[A[j]])*delT/(to[j]-from[j]);
line a(p[A[j]]+J,p[A[j]]+J+I+(p[B[j]]-(p[A[j]]+J))*g);
pt O=p[A[i]];
pt P=perpendicular(O,a),D,pA,pB;
ld d=s(P.x-O.x)+s(P.y-O.y);
if(d>r*r-eps)
continue;
else if(abs(d)<=eps)
D=(a.B-a.A)*r/dis(a.A,a.B);
else
D=T((P-O)*sqrt(r*r/d-));
pA=P+D,pB=P-D;
ld len=dis(a.A,a.B);
ld t1=((pA-a.A)&(a.B-a.A))/len/len*(to[i]-from[i])+from[i];
ld t2=((pB-a.A)&(a.B-a.A))/len/len*(to[i]-from[i])+from[i];
if(t1>t2)
swap(t1,t2);
t1=max(max(from[i],from[j]),t1);
t2=min(min(to[i],to[j]),t2);
if(t2-t1>=eps)
tmp[++tot]=info(t1,t2,n+i,n+j);
}
for(int i=;i<=tot;++i)
{
if((!test(tmp[i].L-*eps))||(!test(tmp[i].R-*eps)))
return false;
if((!test(tmp[i].L+*eps))||(!test(tmp[i].R+*eps)))
return false;
}
return true;
}
int main()
{
freopen("airline.in","r",stdin);
freopen("airline.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=n;++i)
cin>>p[i].x>>p[i].y;
for(int i=;i<=m;++i)
{
cin>>A[i]>>B[i]>>from[i]>>to[i];
++A[i],++B[i];
}
for(int i=;i<=m;++i)
length[i]=dis(p[A[i]],p[B[i]]);
ld L=,R=,mid;
for(int i=;i<=n;++i)
for(int j=i+;j<=n;++j)
R=max(R,dis(p[i],p[j]));
R*=;
while(abs(R-L)>0.000001)
{
mid=(L+R)/;
if(check(mid))
R=mid;
else
L=mid;
}
cout<<fixed<<setprecision()<<mid<<endl;
return ;
}```
View Code

https://www.cnblogs.com/GreenDuck/p/12252853.html