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)且字典序最小。

可以发现,对于某个质数p,它有一个最大的次数k将pk放在尽可能靠后且能够整除原数组中的数字的位置上,便是答案。

虽然数字的值域达到1E18,但我们只需要知道每个数1~1E6之间的质因子是什么以及是哪些,剩下来的一定是大于1E6的质因子且最多只有两个。

由于答案中的质数及其次数彼此间相互独立,1E6以下的质因子可以直接统计,而剩下的可以通过两两间求gcd的方法进行比较。在这种情况下,数字ABA在原数组的前面,B在后面)由于质数次数最多为2,令x=gcd(A,B)B除以x后(对于某个质因子)要么次数为0,要么为1,要么为22要特判一下,如果有这种情况,B要更新当且仅当A==B),乘上gcd(x,B除以x)后即可进行更新。复杂度为O(n2*logMAX+MAX0.333)

当然,若不嫌麻烦的话可套用pollard-rho模板。复杂度为O(n*MAX0.25)

博主在考场上采用了后者。

 

 #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。

我们先二分半径r,考虑怎么进行检验。可以发现,不管是飞机关于机场、飞机关于飞机,它们能相互建立连接的可行时间点组成了一个区间,因此一个想法为求出这个区间,对于特定的端点建图进行检查。

对于飞机关于机场的情况是简单的。根据普通的平面向量知识,可以轻松地求出这个向量(飞机的飞行路线)与圆(圆心机场,半径为r)的两个交点(如果存在的话)。再次利用数量积的知识,可以知道这两个点到出发点的距离,与整个路线长度的比值(当然,这是有方向的)。求完后分别取minmax保证时间确实在航班时间范围内即可(比如说起点在圆里面的情况)。

飞机关于飞机比较麻烦。首先,我们先使得航线A和航线B的速度相等,这样方便下面求解。具体地讲,A向量的模除以时间A的值,要等于B向量的模除以时间的值。然后以飞机A为参考系,飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致,只不过要保证时间要在两个航班时间范围内。

还有一点要注意的是,向量可能经过圆心,这需要判断。

总共有O((n+m)2)个区间,单次建边、检查的复杂度是O((n+m)2)的,因此总复杂度为O((n+m)4logn)

 

 #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
 {
 int size,head[555555];
 bool vis[];
 struct edge
  {
 int to,next;
 }E[555555];
 inline void clear()
  {
 for(int i=;i<=n+m;++i)
 head[i]=;
 for(int i=;i<=size;++i)
 E[i].to=E[i].next=;
 size=;
  }
 inline void add(int u,int v)
  {
 E[++size].to=v;
 E[size].next=head[u];
 head[u]=size;
  }
 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();
 for(int i=head[u];i;i=E[i].next)
  {
 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)
  {
  graph::add(tmp[i].x,tmp[i].y);
  graph::add(tmp[i].y,tmp[i].x);
  }
 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

 

 

 

 

我们先

二分半径r,考虑怎么进行检验。可以发现,不管是飞机关于机场、飞机关于飞机,它们能相互建立连接的可行时间点组成了一个区间,因此一个想法为求出这个区间,对于特定的端点建图进行检查。

对于飞机关于机场的情况是简单的。根据普通的平面向量知识,可以轻松地求出这个向量(飞机的飞行路线)与圆(圆心机场,半径为r)的两个交点(如果存在的话)。再次利用数量积的知识,可以知道这两个点到出发点的距离,与整个路线长度的比值(当然,这是有方向的)。求完后分别取minmax保证时间确实在航班时间范围内即可(比如说起点在圆里面的情况)。

飞机关于飞机比较麻烦。首先,我们先使得航线A和航线B的速度相等,这样方便下面求解。具体地讲,A向量的模除以时间A的值,要等于B向量的模除以时间的值。然后以飞机A为参考系,飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致,只不过要保证时间要在两个航班时间范围内。

还有一点要注意的是,向量可能经过圆心,这需要判断。

总共有O((n+m)2)个区间,单次建边、检查的复杂度是O((n+m)2)的,因此总复杂度为O((n+m)4logn)

版权声明
本文为[GreenDuck]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/GreenDuck/p/12252853.html