题面：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
",q.back());
return 0;
}
six：
刚听完，还没打
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<map> 7 #define int long long 8 #define re register 9 using namespace std; 10 const int mod=1e9+7; 11 int n,num=0,d[100005],ans=0,ys[100005]; 12 int sta[10000005],top=0; 13 int t[100005],cnt[1<<7]; 14 void divi(re int n){ 15 re int nn=n; 16 int p=sqrt(n); 17 for(re int i=2;i<=p;++i){ 18 if(!(nn%i)){ 19 d[++d[0]]=i; 20 t[d[0]]=1<<(d[0]-1); 21 while(!(nn%i)) nn/=i; 22 } 23 } 24 if(nn>1){ 25 d[++d[0]]=nn; 26 t[d[0]]=1<<(d[0]-1); 27 } 28 ys[++ys[0]]=n; 29 for(re int i=2;i*i<=n;++i){ 30 if(!(n%i)){ 31 ys[++ys[0]]=i; 32 if(n/i!=i) ys[++ys[0]]=n/i; 33 } 34 } 35 for(re int i=1;i<=ys[0];++i){ 36 re int res=0; 37 for(re int j=1;j<=d[0];++j) 38 if(ys[i]%d[j]==0) res|=t[j]; 39 ++cnt[res]; 40 } 41 } 42 int zt[7][7],f[1<<22]; 43 void prework(){ 44 re int num=0; 45 for(re int i=1;i<=6;++i){ 46 for(re int j=i;j<=6;++j){ 47 zt[i][j]=zt[j][i]=1<<num; 48 ++num; 49 } 50 } 51 top=0; 52 for(re int i=1;i<(1<<d[0]);++i){ 53 re int res=i; 54 top=0; 55 for(re int j=1;j<=d[0];++j){ 56 if(i&t[j]) sta[++top]=j; 57 } 58 for(re int j=1;j<=top;++j){ 59 for(re int k=j;k<=top;++k){ 60 f[i]|=zt[sta[j]][sta[k]]; 61 } 62 } 63 } 64 } 65 map<pair<int,int>,int>mp; 66 int dfs(int fi,int se){ 67 pair<int,int>p=make_pair(fi,se); 68 if(mp[p]) return mp[p]; 69 for(int i=1;i<(1<<d[0]);++i){ 70 if(f[i]&p.second) continue; 71 int res=p.second; 72 for(int j=1;j<=d[0];++j){ 73 if(!(i&t[j])) continue; 74 for(int k=1;k<=d[0];++k){ 75 if(!(p.first&t[k])) continue; 76 res|=zt[j][k]; 77 } 78 } 79 mp[p]=(mp[p]+cnt[i]*(dfs(p.first|i,res)+1)%mod)%mod; 80 } 81 return mp[p]; 82 } 83 signed main(){ 84 scanf("%lld",&n); 85 divi(n);prework();//exit(0); 86 printf("%lld ",dfs(0,0)); 87 return 0; 88 }
walker：
把坐标等式写出来就是：
$scale*cos heta*px-scale*sin heta*py+dx=nx$
$scale*sin heta*px+scale*cos heta*py+dy=ny$
把$scale*sin heta$和$scale*cos heta$，dx，dy看成四个变量，随机化枚举两组点进行高斯消元，解出4个未知数
因为$sin heta^2+cos heta^2=1$，所以我们可以再解出scale和$ heta$
然后带回验证是否满足$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 %0.7lf %0.7lf %0.7lf ",theta,scale,dx,dy); 61 return 0; 62 } 63 } 64 } 65 } 66 return 0; 67 }