[校内训练20_01_22]ABC
1.给出序列A，求序列B，使得bi|ai,lcm(b1,b2,…,bn)=lcm(a1,a2,…,an)且字典序最小。
可以发现，对于某个质数p，它有一个最大的次数k，将pk放在尽可能靠后且能够整除原数组中的数字的位置上，便是答案。
虽然数字的值域达到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(n2*logMAX+MAX0.333)。
当然，若不嫌麻烦的话可套用pollard-rho模板。复杂度为O(n*MAX0.25)。
博主在考场上采用了后者。
1 #include <cstdio> 2 #include <sstream> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std; 7 8 typedef long long LL; 9 10 const int MAXN = 105; 11 12 LL num[MAXN]; 13 LL common[MAXN]; 14 int n, cs; 15 16 LL gcd(LL a, LL b) 17 { 18 LL tmp; 19 while (b) tmp = a, a = b, b = tmp % b; 20 return a; 21 } 22 23 void solve() 24 { 25 for (int i = 0; i < n; i++){ 26 cs = 0; 27 for (int j = 0; j < n; j++) 28 if (i != j) 29 common[cs ++] = gcd(num[i], num[j]); 30 LL s = 1; 31 for (int j = 0; j < cs; j++){ 32 s *= common[j]; 33 for (int k = j+1; k < cs; k++) 34 common[k] /= gcd(common[j], common[k]); 35 } 36 num[i] /= s; 37 while (true){ 38 LL x = gcd(num[i], s); 39 if (x == 1) 40 break; 41 num[i] *= x; 42 s /= x; 43 } 44 } 45 } 46 47 int main() 48 { 49 freopen("transform.in", "r", stdin); 50 freopen("transform.out", "w", stdout); 51 scanf("%d", &n); 52 for (int i = 0; i < n; i ++) 53 scanf("%lld", &num[i]); 54 solve(); 55 for (int i = 0; i < n; i ++) 56 printf("%lld ", num[i]); 57 printf("\n"); 58 return 0; 59 }
View Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long int ll; 4 typedef long double ld; 5 ll n,a[105],ans[105]; 6 map<ll,ll>cnt,where; 7 namespace math 8 { 9 const int len=10; 10 ll test[len]={2,3,5,7,11,13,17,19,23,29}; 11 ll size,wait[555]; 12 inline ll mul(ll x,ll y,ll mod) 13 { 14 ll d=(ld)x*y/mod; 15 return ((x*y-d*mod)%mod+mod)%mod; 16 } 17 inline ll QPOW(ll x,ll y) 18 { 19 ll ans=1; 20 for(int i=1;i<=y;++i) 21 ans=ans*x; 22 return ans; 23 } 24 inline ll qpow(ll x,ll y,ll mod) 25 { 26 ll ans=1,base=x; 27 while(y) 28 { 29 if(y&1) 30 ans=mul(ans,base,mod); 31 base=mul(base,base,mod); 32 y>>=1; 33 } 34 return ans; 35 } 36 inline bool isPrime(ll p) 37 { 38 for(int i=0;i<len;++i) 39 { 40 if(p<test[i]) 41 return false; 42 else if(p==test[i]) 43 return true; 44 ll x=qpow(test[i],p-1,p),d=p-1; 45 if(x!=1) 46 return false; 47 while(x==1&&d%2==0) 48 { 49 d>>=1; 50 x=qpow(test[i],d,p); 51 if(x!=1&&x!=p-1) 52 return false; 53 } 54 } 55 return true; 56 } 57 ll gcd(ll x,ll y) 58 { 59 if(y==0) 60 return x; 61 return x%y==0?y:gcd(y,x%y); 62 } 63 inline ll f(ll x,int c,ll mod) 64 { 65 return (mul(x,x,mod)+c)%mod; 66 } 67 inline ll find(ll n,int step,int c) 68 { 69 if(n%2==0) 70 return 2; 71 ll x=2,y=2,d=1; 72 while(true) 73 { 74 ll tmpX=x,tmpY=y,d=1; 75 for(int i=1;i<=step;++i) 76 { 77 x=f(x,c,n); 78 y=f(f(y,c,n),c,n); 79 d=mul(d,(x%n-y%n+n)%n,n); 80 } 81 d=gcd(d,n); 82 if(d==1) 83 continue; 84 else if(d!=n) 85 return d; 86 x=tmpX,y=tmpY; 87 for(int i=1;i<=step;++i) 88 { 89 x=f(x,c,n); 90 y=f(f(y,c,n),c,n); 91 d=gcd(n,(x%n-y%n+n)%n); 92 if(d!=1&&d!=n) 93 return d; 94 } 95 return 0; 96 } 97 return -1; 98 } 99 void factor(ll x) 100 { 101 if(isPrime(x)) 102 { 103 wait[++size]=x; 104 return; 105 } 106 ll step=pow(x,0.1)+1,c=0,now=0; 107 while(!now) 108 now=find(x,step,++c); 109 factor(now),factor(x/now); 110 } 111 void pollard(ll x,int num) 112 { 113 size=0; 114 factor(x); 115 map<ll,ll>G; 116 // for(int i=1;i<=size;++i) 117 // cout<<wait[i]<<" "; 118 // cout<<endl; 119 for(int i=1;i<=size;++i) 120 ++G[wait[i]]; 121 for(int i=1;i<=size;++i) 122 { 123 x=wait[i]; 124 if(G[x]>=cnt[x]) 125 { 126 ans[where[x]]/=QPOW(x,cnt[x]); 127 cnt[x]=G[x]; 128 where[x]=num; 129 ans[num]*=QPOW(x,cnt[x]); 130 } 131 } 132 } 133 } 134 inline bool check(int x) 135 { 136 if(x==1) 137 return false; 138 for(int i=2;i*i<=x;++i) 139 if(x%i==0) 140 return false; 141 return true; 142 } 143 int main() 144 { 145 freopen("transform.in","r",stdin); 146 freopen("transform.out","w",stdout); 147 ios::sync_with_stdio(false); 148 cin>>n; 149 for(int i=1;i<=n;++i) 150 { 151 cin>>a[i]; 152 ans[i]=1; 153 math::pollard(a[i],i); 154 } 155 for(int i=1;i<=n;++i) 156 cout<<ans[i]<<" "; 157 cout<<endl; 158 return 0; 159 }
View Code
2.有一些机场和航线，航线是形如点A到点B的直线，飞机会准时从t1出发t2到达，期间匀速直线运动。机场和飞机都配备雷达，雷达有固定范围R，你需要保证在任意时间内，任意在飞行中的飞机能够通过雷达直接或间接地与机场相连，求最小的R。
我们先二分半径r，考虑怎么进行检验。可以发现，不管是飞机关于机场、飞机关于飞机，它们能相互建立连接的可行时间点组成了一个区间，因此一个想法为求出这个区间，对于特定的端点建图进行检查。
对于飞机关于机场的情况是简单的。根据普通的平面向量知识，可以轻松地求出这个向量（飞机的飞行路线）与圆（圆心机场，半径为r）的两个交点（如果存在的话）。再次利用数量积的知识，可以知道这两个点到出发点的距离，与整个路线长度的比值（当然，这是有方向的）。求完后分别取min、max保证时间确实在航班时间范围内即可（比如说起点在圆里面的情况）。
飞机关于飞机比较麻烦。首先，我们先使得航线A和航线B的速度相等，这样方便下面求解。具体地讲，A向量的模除以时间A的值，要等于B向量的模除以时间的值。然后以飞机A为参考系，飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致，只不过要保证时间要在两个航班时间范围内。
还有一点要注意的是，向量可能经过圆心，这需要判断。
总共有O((n+m)2)个区间，单次建边、检查的复杂度是O((n+m)2)的，因此总复杂度为O((n+m)4logn)。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long double ld; 4 const ld eps=1E-9; 5 const ld inf=1E12; 6 int n,m; 7 int A[555],B[555]; 8 ld from[555],to[555],length[555]; 9 struct pt 10 { 11 ld x,y; 12 pt(ld a=0,ld b=0):x(a),y(b){} 13 pt operator+(const pt&A){return pt(x+A.x,y+A.y);} 14 pt operator-(const pt&A){return pt(x-A.x,y-A.y);} 15 pt operator*(const ld&d){return pt(x*d,y*d);} 16 pt operator/(const ld&d){return pt(x/d,y/d);} 17 ld operator*(const pt&A){return x*A.y-y*A.x;} 18 ld operator&(const pt&A){return x*A.x+y*A.y;} 19 void out() 20 { 21 cout<<"("<<x<<","<<y<<")"; 22 } 23 }p[555]; 24 struct line 25 { 26 pt A,B; 27 line(pt a=pt(),pt b=pt()):A(a),B(b){} 28 }; 29 struct info 30 { 31 ld L,R; 32 int x,y; 33 info(ld a=0,ld b=0,int c=0,int d=0):L(a),R(b),x(c),y(d){} 34 }tmp[555555]; 35 inline ld s(ld x){return x*x;} 36 inline pt intersection(line a,line b) 37 { 38 pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A; 39 if(abs(A*B)<=eps) 40 return pt(inf,inf); 41 ld d=-(B*C)/(B*A); 42 return b.A+A*d; 43 } 44 inline pt T(pt A) 45 { 46 return pt(-A.y,A.x); 47 } 48 inline pt perpendicular(pt A,line a) 49 { 50 if(abs((A-a.A)*(A-a.B))<=eps) 51 return A; 52 pt B=A+T(a.B-a.A); 53 return intersection(line(A,B),a); 54 } 55 inline ld dis(pt A,pt B) 56 { 57 return sqrt(s(A.x-B.x)+s(A.y-B.y)); 58 } 59 namespace graph 60 { 61 int size,head[555555]; 62 bool vis[55555]; 63 struct edge 64 { 65 int to,next; 66 }E[555555]; 67 inline void clear() 68 { 69 for(int i=1;i<=n+m;++i) 70 head[i]=0; 71 for(int i=1;i<=size;++i) 72 E[i].to=E[i].next=0; 73 size=0; 74 } 75 inline void add(int u,int v) 76 { 77 E[++size].to=v; 78 E[size].next=head[u]; 79 head[u]=size; 80 } 81 inline bool ok(ld x) 82 { 83 for(int i=1;i<=n+m;++i) 84 vis[i]=0; 85 queue<int>Q; 86 for(int i=1;i<=n;++i) 87 { 88 Q.push(i); 89 vis[i]=1; 90 } 91 while(!Q.empty()) 92 { 93 int u=Q.front(); 94 Q.pop(); 95 for(int i=head[u];i;i=E[i].next) 96 { 97 int v=E[i].to; 98 if(vis[v]) 99 continue; 100 Q.push(v); 101 vis[v]=1; 102 } 103 } 104 for(int i=n+1;i<=n+m;++i) 105 if((!vis[i])&&(from[i-n]-eps<=x&&x<=to[i-n]+eps)) 106 return false; 107 return true; 108 } 109 } 110 int tot; 111 inline bool test(ld x) 112 { 113 graph::clear(); 114 for(int i=1;i<=tot;++i) 115 if(tmp[i].L-eps<=x&&x<=tmp[i].R+eps) 116 { 117 graph::add(tmp[i].x,tmp[i].y); 118 graph::add(tmp[i].y,tmp[i].x); 119 } 120 return graph::ok(x); 121 } 122 inline bool check(ld r) 123 { 124 tot=0; 125 for(int i=1;i<=n;++i) 126 { 127 pt O=p[i]; 128 for(int j=1;j<=m;++j) 129 { 130 line a(p[A[j]],p[B[j]]); 131 pt P=perpendicular(O,a),D,pA,pB; 132 ld d=s(P.x-O.x)+s(P.y-O.y); 133 if(d>r*r-eps) 134 continue; 135 else if(abs(d)<=eps) 136 D=(a.B-a.A)*r/dis(a.A,a.B); 137 else 138 D=T((P-O)*sqrt(r*r/d-1)); 139 pA=P+D,pB=P-D; 140 ld t1=((pA-p[A[j]])&(p[B[j]]-p[A[j]]))/length[j]/length[j]*(to[j]-from[j])+from[j]; 141 ld t2=((pB-p[A[j]])&(p[B[j]]-p[A[j]]))/length[j]/length[j]*(to[j]-from[j])+from[j]; 142 if(t1>t2) 143 swap(t1,t2); 144 t1=max(from[j],t1); 145 t2=min(to[j],t2); 146 if(t2-t1>=eps) 147 tmp[++tot]=info(t1,t2,i,n+j); 148 } 149 } 150 for(int i=1;i<=m;++i) 151 for(int j=1;j<=m;++j) 152 { 153 if(from[i]<=from[j]) 154 continue; 155 ld delT=from[i]-from[j]; 156 ld g=(ld)(to[i]-from[i])/(ld)(to[j]-from[j]-delT); 157 pt I=p[A[i]]-p[B[i]]; 158 pt J=(p[B[j]]-p[A[j]])*delT/(to[j]-from[j]); 159 line a(p[A[j]]+J,p[A[j]]+J+I+(p[B[j]]-(p[A[j]]+J))*g); 160 pt O=p[A[i]]; 161 pt P=perpendicular(O,a),D,pA,pB; 162 ld d=s(P.x-O.x)+s(P.y-O.y); 163 if(d>r*r-eps) 164 continue; 165 else if(abs(d)<=eps) 166 D=(a.B-a.A)*r/dis(a.A,a.B); 167 else 168 D=T((P-O)*sqrt(r*r/d-1)); 169 pA=P+D,pB=P-D; 170 ld len=dis(a.A,a.B); 171 ld t1=((pA-a.A)&(a.B-a.A))/len/len*(to[i]-from[i])+from[i]; 172 ld t2=((pB-a.A)&(a.B-a.A))/len/len*(to[i]-from[i])+from[i]; 173 if(t1>t2) 174 swap(t1,t2); 175 t1=max(max(from[i],from[j]),t1); 176 t2=min(min(to[i],to[j]),t2); 177 if(t2-t1>=eps) 178 tmp[++tot]=info(t1,t2,n+i,n+j); 179 } 180 for(int i=1;i<=tot;++i) 181 { 182 if((!test(tmp[i].L-2*eps))||(!test(tmp[i].R-2*eps))) 183 return false; 184 if((!test(tmp[i].L+2*eps))||(!test(tmp[i].R+2*eps))) 185 return false; 186 } 187 return true; 188 } 189 int main() 190 { 191 freopen("airline.in","r",stdin); 192 freopen("airline.out","w",stdout); 193 ios::sync_with_stdio(false); 194 cin>>n>>m; 195 for(int i=1;i<=n;++i) 196 cin>>p[i].x>>p[i].y; 197 for(int i=1;i<=m;++i) 198 { 199 cin>>A[i]>>B[i]>>from[i]>>to[i]; 200 ++A[i],++B[i]; 201 } 202 for(int i=1;i<=m;++i) 203 length[i]=dis(p[A[i]],p[B[i]]); 204 ld L=0,R=0,mid; 205 for(int i=1;i<=n;++i) 206 for(int j=i+1;j<=n;++j) 207 R=max(R,dis(p[i],p[j])); 208 R*=2; 209 while(abs(R-L)>0.000001) 210 { 211 mid=(L+R)/2; 212 if(check(mid)) 213 R=mid; 214 else 215 L=mid; 216 } 217 cout<<fixed<<setprecision(4)<<mid<<endl; 218 return 0; 219 }
View Code
我们先
二分半径r，考虑怎么进行检验。可以发现，不管是飞机关于机场、飞机关于飞机，它们能相互建立连接的可行时间点组成了一个区间，因此一个想法为求出这个区间，对于特定的端点建图进行检查。
对于飞机关于机场的情况是简单的。根据普通的平面向量知识，可以轻松地求出这个向量（飞机的飞行路线）与圆（圆心机场，半径为r）的两个交点（如果存在的话）。再次利用数量积的知识，可以知道这两个点到出发点的距离，与整个路线长度的比值（当然，这是有方向的）。求完后分别取min、max保证时间确实在航班时间范围内即可（比如说起点在圆里面的情况）。
飞机关于飞机比较麻烦。首先，我们先使得航线A和航线B的速度相等，这样方便下面求解。具体地讲，A向量的模除以时间A的值，要等于B向量的模除以时间的值。然后以飞机A为参考系，飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致，只不过要保证时间要在两个航班时间范围内。
还有一点要注意的是，向量可能经过圆心，这需要判断。
总共有O((n+m)2)个区间，单次建边、检查的复杂度是O((n+m)2)的，因此总复杂度为O((n+m)4logn)。
版权声明：本文为GreenDuck原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。