【Heaven Cow与God Bull】题解

题目

Description

__int64 ago,there's a heaven cow called sjy...
A god bull named wzc fell in love with her...
As an OI & MOer,wzc gave sjy a quesiton...
给定一个整数n，求一个整数m，满足m<=n，并且m/phi(m)的值最大。
注：phi(m)代表m的欧拉函数，即不大于m且与m互质的数的个数。

Input

第一行是一个整数T，表示该测试点有T组数据。
接下来T行，每行一个整数n，意义如上所述。

Output

输出一共T行，每行一个整数m。
若对于某个n，有不止一个满足条件的m，则输出最小的m。

Sample Input

1
10

Sample Output

6

Data Constraint

对于10%的数据, n<=1000
对于30%的数据, n<=10^10
对于60%的数据, n<=10^2000
对于100%的数据，T<=100，n<=10^25000。

---

分析

设pi为质数，m=p1^e1·p2e2·p3^e3····。
我们首先来化简一下m/φ(m)，容易得出m/φ(m)=(p1-1)(p2-1)(p3-1)···/p1·p2·p3····。
易证当p2>p1时，(p1-1)/p1>(p2-1)/p2，如果m取前k个质数的乘积，答案一定更优。答案就是最大的p1·p2·p3····。
如果边做边求p1·p2·p3····显然是不行的，所以先预处理p1·p2·p3····。大概60000以内的质数就可以，有6057个。为了缩短时间，高精度我压了11位，有点小恶心，事实上速度还是挺快的。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647;
const long long mo=100000000000;
using namespace std;
long long b[6500][2500],zs[6500],t,n,m,a[2500];
char s[100000];
int times(long long x,long long y,long value)
{
	long i,j,k,l;
	for(i=1;i<=b[x][0];i++)
	{
		b[y][i]+=b[x][i]*value;
		b[y][i+1]+=b[y][i]/mo;
		b[y][i]%=mo;
	}
	b[y][0]=b[x][0];
	if(b[y][b[y][0]+1]>0)
		b[y][0]++;
}
int bj(long long a[2500],long long b[2500])
{
	if(b[0]>a[0]) return true;
		if(b[0]<a[0]) return false;
			else
			{
				for(long long i=b[0];i>=1;i--)
				{
					if(b[i]>a[i]) return true;
						if(b[i]<a[i]) return false;
				}
			}
	return false;
}
int main()
{
	scanf("%lld
",&t);
	long long i,j,k,l,x,y;
	for(i=2;i<=60000;i++)
	{
		bool q=true;
		for(j=2;j<=(long long)(sqrt(i));j++)
		{
			if(!(i%j)) q=false;
		}
		if(q)
		{
			zs[++zs[0]]=i;
		}
	}
	b[0][0]=1;
	b[0][1]=1;
	for(i=1;i<=zs[0];i++)//预处理
	{
		times(i-1,i,zs[i]);
	}
	while(t--)
	{
		scanf("%s
",s);
		a[0]=0;
		k=0;
		int len=strlen(s);
		l=1;
		for(i=1;i<=len;i++)
		{
			k=k+(s[len-i]-48)*l;
			l*=10;
			if(l==mo)
			{
				a[++a[0]]=k;
				l=1;
				k=0;
			}
		}
		if(k)
			a[++a[0]]=k;
		for(i=1;i<=zs[0];i++)//O(6057)求答案。如果还想快点，可以二分
		{
			if(bj(a,b[i]))
			{
				for(j=b[i-1][0];j>=1;j--)
				{
					if(j!=b[i-1][0])
						printf("%011lld",b[i-1][j]);
							else
								printf("%lld",b[i-1][j]);
				}
				break;
			}
		}
		printf("
");
	}
}