首页 > 代码库 > 【P1203】买花

【P1203】买花

2024-08-12 15:20:41   219人阅读

我先在已经弱到连高精乘单精都能写错的地步了QAQ

原题：

求一个小于等于N的数M，使得phi(M)/M最小，
其中phi(M)是与M互质且比M小的数的个数。
例如phi(4)=2，因为1，3和4互质。

N<=10^40

 

先推欧拉函数打表，发现答案一定是乘积<=m的前k个质数的乘积（比如50的答案就是2*3*5<=50)

然后就是高精水体

然而我写了2h QAQ，果然实力是会随着时间的推移降低的QAQ

主要错误就是关于乘出来结果的长度的问题，这个长度要在a[i]>=10往后推得时候变推边更新，不能先全部算完了再更新，因为推完后可能会因为%=10而出现中间有0的情况，这时候推长度推到这里就断了，但是边推边更新就不会出现这种情况，因为还没%=10，不会==0

我好弱啊QAQ

代码：

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 void read_big(int *x,int &lx){lx=0;  char ch=getchar(); 8     while(ch<‘0‘||ch>‘9‘)  ch=getchar(); 9     while(ch>=‘0‘&&ch<=‘9‘){  x[++lx]=ch-‘0‘;  ch=getchar();}10 }11 int n[110],ln;12 int a[110],la,b[110],lb,c[110];13 bool kang[1100000];  int zhi[1100000],ztop=0;14 void shai(){15     memset(kang,0,sizeof(kang));16     for(int i=2;i<=1000000;i++)if(!kang[i]){17         zhi[++ztop]=i;18         int temp=1;  while(i*(temp+1)<=1000000)  kang[i*(++temp)]=true;19     }20 }21 bool bi(int *x,int lx,int *y,int ly){22     if(lx!=ly)  return (lx>ly);23     for(int i=lx;i>=1;i--)if(x[i]!=y[i])  return (x[i]>y[i]);24     return false;25 }26 void cheng(int *x,int &lx,int y){27     for(int i=1;i<=lx;i++)  x[i]*=y;28     for(int i=1;i<=lx;i++)  x[i+1]+=x[i]/10,x[i]%=10;29     for(;a[lx+1];lx++)  x[lx]+=x[lx]/10,x[lx]%=10;30 }31 int main(){//freopen("ddd.in","r",stdin);32     shai();33     read_big(c,ln);34     for(int i=ln;i>=1;i--)  n[i]=c[ln-i+1];35     a[la=1]=1;36     for(int i=1;i<=10000;i++){37         lb=la;38         for(int j=1;j<=lb;j++)  b[j]=a[j];39         cheng(a,la,zhi[i]);40         if(bi(a,la,n,ln)){  for(int j=lb;j>=1;j--)cout<<b[j];  cout<<endl;  return 0;}41     }42     return 0;43 }
View Code

 

【P1203】买花


联系
我们