描述 Description
给定一个整数n，求一个整数m，满足m<=n，并且m/phi(m)的值最大。
注：phi(m)代表m的欧拉函数，即不大于m且与m互质的数的个数。
注：phi(m)代表m的欧拉函数，即不大于m且与m互质的数的个数。
题解：
m/phi（m) 很容易化成 连积（p/（p-1）） p|m
所以就很简单了，将最小的质数乘起来，直到>n，输出前一个。
因为保证最小所以只乘一次，因为p/（p-1）单调减，所以从小的开始选。
高精度写错搞了好久，然后有卡了几次时才过了
代码：
m/phi（m) 很容易化成 连积（p/（p-1）） p|m
所以就很简单了，将最小的质数乘起来，直到>n，输出前一个。
因为保证最小所以只乘一次，因为p/（p-1）单调减，所以从小的开始选。
高精度写错搞了好久，然后有卡了几次时才过了
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 100000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 10
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,tot,p[maxn];
bool v[maxn];
char ch[maxn];
class bigg{
public:
int num[maxn],len;
bigg()
{
memset(num,,sizeof(num));
len=;
}
inline bigg operator =(const bigg &b)
{
memset(num,,sizeof(num));
len=b.len;
for1(i,len)num[i]=b.num[i];
return(*this);
}
inline bigg operator =(int b)
{
memset(num,,sizeof(num));
len=;
while(b){num[++len]=b%mod;b/=mod;}
return(*this);
}
inline bigg operator *(int b)
{
for1(i,len)num[i]*=b;
for1(i,len)
{
num[i+]+=num[i]/mod;
num[i]%=mod;
if(num[len+])len++;
}
return(*this);
}
inline bool operator <(const bigg&b)
{
if(len!=b.len)return len<b.len;
for3(i,len,)if(num[i]!=b.num[i])return num[i]<b.num[i];
return ;
}
inline void print()
{
printf("%d",num[len]);
for3(i,len-,)printf("%d",num[i]);printf("\n");
}
};
bigg a[],b,c[];
int rk[];
bool cmp(int x,int y){return a[x]<a[y];}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
for2(i,,maxn)
{
if(!v[i])p[++tot]=i;
for1(j,tot)
{
int k=p[j]*i;
if(k>maxn)break;
v[k]=;
if(i%p[j]==)break;
}
}
n=read();
for1(i,n)
{
scanf("%s",ch+);
a[i].len=strlen(ch+);
for1(j,a[i].len)a[i].num[j]=ch[a[i].len+-j]-'';
rk[i]=i;
}
sort(rk+,rk+n+,cmp);
int j=;
b=j;
//for1(i,100)b=b*p[i],b.print();
for1(i,n)
{
c[rk[i]]=c[rk[i-]];
while(b<a[rk[i]])c[rk[i]]=b,b=b*p[j++];
//b.print();
}
//for1(i,n)a[rk[i]].print(),c[rk[i]].print();
for1(i,n)c[i].print();
return ;
}
不知道每组询问暴力求会不会T，我为了保险拍了个序233
UPD：这个程序交到bz也T了。。。TAT
无奈看了lyd的程序，居然预处理压了8位！
orzz
憋了1h+终于写出来了，二分+预处理。。。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 100000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 100000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,tot,p[maxn];
bool v[maxn];
char s[maxn];
class bigg{
public:
int num[],len;
bigg()
{
memset(num,,sizeof(num));
len=;
}
inline bigg operator =(const bigg &b)
{
memset(num,,sizeof(num));
len=b.len;
for1(i,len)num[i]=b.num[i];
return(*this);
}
inline bigg operator =(int b)
{
memset(num,,sizeof(num));
len=;
while(b){num[++len]=b%mod;b/=mod;}
return(*this);
}
inline bigg operator *(int b)
{
ll x=;
for1(i,len)
{
x+=(ll)num[i]*b;
num[i]=x%mod;
x/=mod;
}
if(x)num[++len]=x;
return(*this);
}
inline bool operator <(const bigg&b)
{
if(len!=b.len)return len<b.len;
for3(i,len,)if(num[i]!=b.num[i])return num[i]<b.num[i];
return ;
}
inline void print()
{
printf("%d",num[len]);
for3(i,len-,)printf("%08d",num[i]);printf("\n");
}
};
bigg a,b[];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
for2(i,,maxn)
{
if(!v[i])p[++tot]=i;
for1(j,tot)
{
int k=p[j]*i;
if(k>maxn)break;
v[k]=;
if(i%p[j]==)break;
}
}
b[]=;
for1(i,)b[i]=b[i-],b[i]=b[i]*p[i];
int cs=read();
while(cs--)
{
memset(s,,sizeof(s));
scanf("%s",s);
n=strlen(s);
reverse(s,s+n);
for0(i,n-)s[i]-='';
a.len=(n+)/;
for0(i,a.len-)
a.num[i+]=s[i*]+*s[i*+]+*s[i*+]+*s[i*+]+*(s[i*+]+*s[i*+]+*s[i*+]+*s[i*+]);
int l=,r=,mid;
while(l<=r)
{
mid=(l+r)>>;
if(b[mid]<a)l=mid+;else r=mid-;
}
b[r].print();
}
return ;
}
UPD：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 100000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 100000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,tot,p[maxn];
bool v[maxn];
char s[maxn];
class bigg{
public:
int num[],len;
bigg()
{
memset(num,,sizeof(num));
len=;
}
inline bigg operator =(const bigg &b)
{
memset(num,,sizeof(num));
len=b.len;
for1(i,len)num[i]=b.num[i];
return(*this);
}
inline bigg operator =(int b)
{
memset(num,,sizeof(num));
len=;
while(b){num[++len]=b%mod;b/=mod;}
return(*this);
}
inline bigg operator *(int b)
{
ll x=;
for1(i,len)
{
x+=(ll)num[i]*b;
num[i]=x%mod;
x/=mod;
}
if(x)num[++len]=x;
return(*this);
}
inline bool operator <(const bigg&b)
{
if(len!=b.len)return len<b.len;
for3(i,len,)if(num[i]!=b.num[i])return num[i]<b.num[i];
return ;
}
inline void print()
{
printf("%d",num[len]);
for3(i,len-,)printf("%08d",num[i]);printf("\n");
}
};
bigg a[],b,c[];
int rk[];
bool cmp(int x,int y){return a[x]<a[y];}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
for2(i,,maxn)
{
if(!v[i])p[++tot]=i;
for1(j,tot)
{
int k=p[j]*i;
if(k>maxn)break;
v[k]=;
if(i%p[j]==)break;
}
}
n=read();
for1(j,n)
{
memset(s,,sizeof(s));
scanf("%s",s);
m=strlen(s);
reverse(s,s+m);
for0(i,m-)s[i]-='';
a[j].len=(m+)/;
for0(i,a[j].len-)
a[j].num[i+]=s[i*]+*s[i*+]+*s[i*+]+*s[i*+]+*(s[i*+]+*s[i*+]+*s[i*+]+*s[i*+]);
rk[j]=j;
}
sort(rk+,rk+n+,cmp);
int j=;
b=;
for1(i,n)
{
c[rk[i]]=c[rk[i-]];
while(b<a[rk[i]])c[rk[i]]=b,b=b*p[j++];
}
for1(i,n)c[i].print();
return ;
}
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
用我的方法+压8位 怒排rank3
代码：