1.给出序列A，求序列B，使得b|a,lcm(b,b,...,b)=lcm(a,a,...,a)且字典序最小。
可以发现，对于某个质数p，它有一个最大的次数k，将p放在尽可能靠后且能够整除原数组中的数字的位置上，便是答案。
虽然数字的值域达到1E18，但我们只需要知道每个数1~1E6之间的质因子是什么以及是哪些，剩下来的一定是大于1E6的质因子且最多只有两个。
由于答案中的质数及其次数彼此间相互独立，1E6以下的质因子可以直接统计，而剩下的可以通过两两间求gcd的方法进行比较。在这种情况下，数字A和B（A在原数组的前面，B在后面）由于质数次数最多为2，令x=gcd(A,B)，B除以x后（对于某个质因子）要么次数为0，要么为1，要么为2（2要特判一下，如果有这种情况，B要更新当且仅当A==B），乘上gcd(x,B除以x后)后即可进行更新。复杂度为O(n*logMAX+MAX)。
当然，若不嫌麻烦的话可套用pollard-rho模板。复杂度为O(n*MAX)。
博主在考场上采用了后者。
#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 ;
}
#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 ;
}
2.有一些机场和航线，航线是形如点A到点B的直线，飞机会准时从t1出发t2到达，期间匀速直线运动。机场和飞机都配备雷达，雷达有固定范围R，你需要保证在任意时间内，任意在飞行中的飞机能够通过雷达直接或间接地与机场相连，求最小的R。
我们先二分半径r，考虑怎么进行检验。可以发现，不管是飞机关于机场、飞机关于飞机，它们能相互建立连接的可行时间点组成了一个区间，因此一个想法为求出这个区间，对于特定的端点建图进行检查。
对于飞机关于机场的情况是简单的。根据普通的平面向量知识，可以轻松地求出这个向量（飞机的飞行路线）与圆（圆心机场，半径为r）的两个交点（如果存在的话）。再次利用数量积的知识，可以知道这两个点到出发点的距离，与整个路线长度的比值（当然，这是有方向的）。求完后分别取min、max保证时间确实在航班时间范围内即可（比如说起点在圆里面的情况）。
飞机关于飞机比较麻烦。首先，我们先使得航线A和航线B的速度相等，这样方便下面求解。具体地讲，A向量的模除以时间A的值，要等于B向量的模除以时间的值。然后以飞机A为参考系，飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致，只不过要保证时间要在两个航班时间范围内。
还有一点要注意的是，向量可能经过圆心，这需要判断。
总共有O((n+m))个区间，单次建边、检查的复杂度是O((n+m))的，因此总复杂度为O((n+m)logn)。
#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[];
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[];
bool vis[];
struct edge
{
int to,next;
}E[];
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 ;
}
我们先
二分半径r，考虑怎么进行检验。可以发现，不管是飞机关于机场、飞机关于飞机，它们能相互建立连接的可行时间点组成了一个区间，因此一个想法为求出这个区间，对于特定的端点建图进行检查。
对于飞机关于机场的情况是简单的。根据普通的平面向量知识，可以轻松地求出这个向量（飞机的飞行路线）与圆（圆心机场，半径为r）的两个交点（如果存在的话）。再次利用数量积的知识，可以知道这两个点到出发点的距离，与整个路线长度的比值（当然，这是有方向的）。求完后分别取min、max保证时间确实在航班时间范围内即可（比如说起点在圆里面的情况）。
飞机关于飞机比较麻烦。首先，我们先使得航线A和航线B的速度相等，这样方便下面求解。具体地讲，A向量的模除以时间A的值，要等于B向量的模除以时间的值。然后以飞机A为参考系，飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致，只不过要保证时间要在两个航班时间范围内。
还有一点要注意的是，向量可能经过圆心，这需要判断。
总共有O((n+m))个区间，单次建边、检查的复杂度是O((n+m))的，因此总复杂度为O((n+m)logn)。