题面：https://www.cnblogs.com/Juve/articles/11733280.html
smooth：
暴力强筛到7e7有60分。。。
正解：
维护一个队列，存所有的B-光滑数，维护B个指针，
因为所有的B-光滑数都有1，所以队列中先插1，所有指针只向1的位置
然后扫描B个指针，找出指针指向元素乘上对应质数的最小值更新队列
以B=4为例，最初所有指针只向1，然后扫描指针发现2×1最小，把2放入队列，1指针只向2
下一次扫描所有指针的结果为：4，3，5，7，其中3最小，3入队，2指针只向2
下一次：4，6，5，7，其中5最小，5入队，3指针（5的指针）指向2
在一次：4，6，10，7，其中4如队，1指针指向3
然后下一次发现是6，6，10，7，有两个相同的6，为了去重，1，2指针都要后移
然后模拟这个过程即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
#define int long long
using namespace std;
const int MAXN=1e7+5;
int b,k,sm[MAXN],p[17];
int prime[17]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
deque<int>q;
signed main(){
scanf("%lld%lld",&b,&k);
q.push_front(0),q.push_back(1);
for(int i=1;i<=b;++i) p[i]=1;
for(int i=2;i<=k;++i){
int minn=1e18;
for(int j=1;j<=b;++j){
if(q[p[j]]*prime[j]==q[i-1]) ++p[j];
minn=min(minn,q[p[j]]*prime[j]);
}
q.push_back(minn);
}
printf("%lld\n",q.back());
return 0;
}
six：
刚听完，还没打
walker：
把坐标等式写出来就是：
$scale*cos\theta*px-scale*sin\theta*py+dx=nx$
$scale*sin\theta*px+scale*cos\theta*py+dy=ny$
把$scale*sin\theta$和$scale*cos\theta$，dx，dy看成四个变量，随机化枚举两组点进行高斯消元，解出4个未知数
因为$sin\theta^2+cos\theta^2=1$，所以我们可以再解出scale和$\theta$
然后带回验证是否满足$\frac{n}{2}$组解
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int MAXN=1e5+5; 8 int n; 9 double nx[MAXN],ny[MAXN],px[MAXN],py[MAXN]; 10 double a[5][6]; 11 void gauss(int n){ 12 for(int i=1;i<=n;i++){ 13 int p=i; 14 for(int j=i+1;j<=n;j++) 15 if(fabs(a[j][i])>fabs(a[p][i])) p=j; 16 for(int j=1;j<=n+1;j++) 17 swap(a[p][j],a[i][j]); 18 if(fabs(a[i][i])<1e-8)continue; 19 double tmp=a[i][i]; 20 for(int j=1;j<=n+1;j++) 21 a[i][j]/=tmp; 22 for(int j=1;j<=n;j++) 23 if(i!=j){ 24 double tmp=a[j][i]; 25 for(int k=1;k<=n+1;k++)a[j][k]-=a[i][k]*tmp; 26 } 27 } 28 for(int i=n;i;--i) 29 for(int j=i-1;j;--j) 30 a[j][n+1]-=a[i][n+1]*a[j][i]/a[i][i]; 31 for(int i=n;i;--i) 32 a[i][n+1]/=a[i][i]; 33 } 34 void make(int p1,int p2){ 35 a[1][1]=px[p1],a[1][2]=-py[p1],a[1][3]=1.0,a[1][4]=0.0,a[1][5]=nx[p1], 36 a[2][1]=py[p1],a[2][2]=px[p1],a[2][3]=0.0,a[2][4]=1.0,a[2][5]=ny[p1], 37 a[3][1]=px[p2],a[3][2]=-py[p2],a[3][3]=1.0,a[3][4]=0.0,a[3][5]=nx[p2], 38 a[4][1]=py[p2],a[4][2]=px[p2],a[4][3]=0.0,a[4][4]=1.0,a[4][5]=ny[p2]; 39 } 40 signed main(){ 41 scanf("%d",&n); 42 srand(time(0)); 43 for(int i=1;i<=n;++i) scanf("%lf%lf%lf%lf",&px[i],&py[i],&nx[i],&ny[i]); 44 while(1){ 45 int p1=rand()%n+1,p2=rand()%n+1,num=0; 46 while(p1==p2) p2=rand()%n+1; 47 make(p1,p2),gauss(4); 48 double scale=sqrt(a[1][5]*a[1][5]+a[2][5]*a[2][5]); 49 if(scale>10||scale<0) continue; 50 double co=a[1][5]/scale,si=a[2][5]/scale; 51 double ta=si/co; 52 double theta=atan(ta); 53 if(fabs(sin(theta)-si)>1e-7) theta+=3.141592653589; 54 if(theta<-1e-8) theta+=3.141592653589*2; 55 double dx=a[3][5],dy=a[4][5]; 56 for(int i=1;i<=n;++i){ 57 if(fabs(scale*co*px[i]-scale*si*py[i]+dx-nx[i])<1e-5&&fabs(scale*si*px[i]+scale*co*py[i]+dy-ny[i])<1e-5){ 58 ++num; 59 if(num>=(n+1)/2){ 60 printf("%0.7lf\n%0.7lf\n%0.7lf %0.7lf\n",theta,scale,dx,dy); 61 return 0; 62 } 63 } 64 } 65 } 66 return 0; 67 }
原文：https://www.cnblogs.com/Juve/p/11733204.html
