「Poetize3」Heaven Cow与God Bull

描述 Description

给定一个整数n，求一个整数m，满足m<=n，并且m/phi(m)的值最大。
注：phi(m)代表m的欧拉函数，即不大于m且与m互质的数的个数。

题解：
m/phi（m) 很容易化成连积（p/（p-1）） p|m
所以就很简单了，将最小的质数乘起来，直到>n，输出前一个。
因为保证最小所以只乘一次，因为p/（p-1）单调减，所以从小的开始选。
高精度写错搞了好久，然后有卡了几次时才过了
代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 100000
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 10
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 int n,m,tot,p[maxn];
 61 bool v[maxn];
 62 char ch[maxn];
 63 class bigg{
 64 public:
 65     int num[maxn],len;
 66     bigg()
 67     {
 68         memset(num,0,sizeof(num));
 69         len=0;
 70     }
 71     inline bigg operator =(const bigg &b)
 72     {
 73         memset(num,0,sizeof(num));
 74         len=b.len;
 75         for1(i,len)num[i]=b.num[i];
 76         return(*this);
 77     }
 78     inline bigg operator =(int b)
 79     {
 80         memset(num,0,sizeof(num));
 81         len=0;
 82         while(b){num[++len]=b%mod;b/=mod;}
 83         return(*this);
 84     }
 85     inline bigg operator *(int b)
 86     {
 87         for1(i,len)num[i]*=b;
 88         for1(i,len)
 89         {
 90             num[i+1]+=num[i]/mod;
 91             num[i]%=mod;
 92             if(num[len+1])len++;
 93         }
 94         return(*this);
 95     }
 96     inline bool operator <(const bigg&b)
 97    {
 98       if(len!=b.len)return len<b.len;
 99       for3(i,len,1)if(num[i]!=b.num[i])return num[i]<b.num[i];
100       return 1;
101    }
102     inline void print()
103     {
104         printf("%d",num[len]);
105         for3(i,len-1,1)printf("%d",num[i]);printf("
");
106     }
107 };
108 bigg a[105],b,c[105];
109 int rk[105];
110 bool cmp(int x,int y){return a[x]<a[y];}
111 
112 int main()
113 
114 {
115 
116     freopen("input.txt","r",stdin);
117 
118     freopen("output.txt","w",stdout);
119     for2(i,2,maxn)
120     {
121         if(!v[i])p[++tot]=i;
122         for1(j,tot)
123         {
124             int k=p[j]*i;
125             if(k>maxn)break;
126             v[k]=1;
127             if(i%p[j]==0)break;
128         }
129     }
130 
131     n=read();
132     for1(i,n)
133     {
134         scanf("%s",ch+1);
135         a[i].len=strlen(ch+1);
136         for1(j,a[i].len)a[i].num[j]=ch[a[i].len+1-j]-'0';
137         rk[i]=i;
138     }    
139     sort(rk+1,rk+n+1,cmp);
140     int j=1;
141     b=j;
142     //for1(i,100)b=b*p[i],b.print();
143     for1(i,n)
144     {
145         c[rk[i]]=c[rk[i-1]];
146         while(b<a[rk[i]])c[rk[i]]=b,b=b*p[j++];
147         //b.print();
148     }
149     //for1(i,n)a[rk[i]].print(),c[rk[i]].print();
150     for1(i,n)c[i].print();
151 
152     return 0;
153 
154 }

View Code

不知道每组询问暴力求会不会T，我为了保险拍了个序233

UPD：这个程序交到bz也T了。。。TAT

无奈看了lyd的程序，居然预处理压了8位！

orzz

憋了1h+终于写出来了，二分+预处理。。。

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 100000
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 100000000
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 int n,m,tot,p[maxn];
 61 bool v[maxn];
 62 char s[maxn];
 63 class bigg{
 64 public:
 65     int num[3500],len;
 66     bigg()
 67     {
 68         memset(num,0,sizeof(num));
 69         len=0;
 70     }
 71     inline bigg operator =(const bigg &b)
 72     {
 73         memset(num,0,sizeof(num));
 74         len=b.len;
 75         for1(i,len)num[i]=b.num[i];
 76         return(*this);
 77     }
 78     inline bigg operator =(int b)
 79     {
 80         memset(num,0,sizeof(num));
 81         len=0;
 82         while(b){num[++len]=b%mod;b/=mod;}
 83         return(*this);
 84     }
 85     inline bigg operator *(int b)
 86     {
 87        ll x=0;
 88         for1(i,len)
 89         {
 90             x+=(ll)num[i]*b;
 91             num[i]=x%mod;
 92             x/=mod;
 93         }
 94         if(x)num[++len]=x;
 95         return(*this);
 96     }
 97     inline bool operator <(const bigg&b)
 98    {
 99       if(len!=b.len)return len<b.len;
100       for3(i,len,1)if(num[i]!=b.num[i])return num[i]<b.num[i];
101       return 1;
102    }
103     inline void print()
104     {
105         printf("%d",num[len]);
106         for3(i,len-1,1)printf("%08d",num[i]);printf("
");
107     }
108 };
109 bigg a,b[6005];
110 int main()
111 {
112     freopen("input.txt","r",stdin);
113     freopen("output.txt","w",stdout);
114     for2(i,2,maxn)
115     {
116         if(!v[i])p[++tot]=i;
117         for1(j,tot)
118         {
119             int k=p[j]*i;
120             if(k>maxn)break;
121             v[k]=1;
122             if(i%p[j]==0)break;
123         }
124     }
125     b[0]=1;
126     for1(i,6000)b[i]=b[i-1],b[i]=b[i]*p[i];
127     int cs=read();
128     while(cs--)
129     {
130         memset(s,0,sizeof(s));
131         scanf("%s",s);
132         n=strlen(s);
133         reverse(s,s+n);
134         for0(i,n-1)s[i]-='0';
135         a.len=(n+7)/8;
136         for0(i,a.len-1)
137         a.num[i+1]=s[i*8]+10*s[i*8+1]+100*s[i*8+2]+1000*s[i*8+3]+10000*(s[i*8+4]+10*s[i*8+5]+100*s[i*8+6]+1000*s[i*8+7]);
138         int l=1,r=6000,mid;
139         while(l<=r)
140         {
141             mid=(l+r)>>1;
142             if(b[mid]<a)l=mid+1;else r=mid-1;
143         }
144         b[r].print();
145     }    
146     return 0;
147 
148 }

View Code

UPD：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 100000
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 100000000
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 int n,m,tot,p[maxn];
 61 bool v[maxn];
 62 char s[maxn];
 63 class bigg{
 64 public:
 65     int num[5000],len;
 66     bigg()
 67     {
 68         memset(num,0,sizeof(num));
 69         len=0;
 70     }
 71     inline bigg operator =(const bigg &b)
 72     {
 73         memset(num,0,sizeof(num));
 74         len=b.len;
 75         for1(i,len)num[i]=b.num[i];
 76         return(*this);
 77     }
 78     inline bigg operator =(int b)
 79     {
 80         memset(num,0,sizeof(num));
 81         len=0;
 82         while(b){num[++len]=b%mod;b/=mod;}
 83         return(*this);
 84     }
 85     inline bigg operator *(int b)
 86     {
 87        ll x=0;
 88         for1(i,len)
 89         {
 90             x+=(ll)num[i]*b;
 91             num[i]=x%mod;
 92             x/=mod;
 93         }
 94         if(x)num[++len]=x;
 95         return(*this);
 96     }
 97     inline bool operator <(const bigg&b)
 98    {
 99       if(len!=b.len)return len<b.len;
100       for3(i,len,1)if(num[i]!=b.num[i])return num[i]<b.num[i];
101       return 1;
102    }
103     inline void print()
104     {
105         printf("%d",num[len]);
106         for3(i,len-1,1)printf("%08d",num[i]);printf("
");
107     }
108 };
109 bigg a[105],b,c[105];
110 int rk[105];
111 bool cmp(int x,int y){return a[x]<a[y];}
112 
113 int main()
114 
115 {
116 
117     freopen("input.txt","r",stdin);
118 
119     freopen("output.txt","w",stdout);
120     for2(i,2,maxn)
121     {
122         if(!v[i])p[++tot]=i;
123         for1(j,tot)
124         {
125             int k=p[j]*i;
126             if(k>maxn)break;
127             v[k]=1;
128             if(i%p[j]==0)break;
129         }
130     }
131 
132     n=read();
133     for1(j,n)
134     {
135         memset(s,0,sizeof(s));
136         scanf("%s",s);
137         m=strlen(s);
138         reverse(s,s+m);
139         for0(i,m-1)s[i]-='0';
140         a[j].len=(m+7)/8;
141         for0(i,a[j].len-1)
142         a[j].num[i+1]=s[i*8]+10*s[i*8+1]+100*s[i*8+2]+1000*s[i*8+3]+10000*(s[i*8+4]+10*s[i*8+5]+100*s[i*8+6]+1000*s[i*8+7]);
143         rk[j]=j;
144     }    
145     sort(rk+1,rk+n+1,cmp);
146     int j=1;
147     b=1;
148     for1(i,n)
149     {
150         c[rk[i]]=c[rk[i-1]];
151         while(b<a[rk[i]])c[rk[i]]=b,b=b*p[j++];
152     }
153     for1(i,n)c[i].print();
154 
155     return 0;
156 
157 }

View Code

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

用我的方法+压8位怒排rank3

代码：