[数论][高精度]Heaven Cow与God Bull

本文主要是介绍[数论][高精度]Heaven Cow与God Bull，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

__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

Sample Output
6

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

分析

我们把题面的式子化成：

p 1 p 1 - 1 \times p 2 p 2 - 1 \times . . . \times p k p k - 1

$\frac{p1}{p1-1}\times\frac{p2}{p2-1}\times...\times\frac{pk}{pk-1}$
显然质因子越多越少（同时我们也知道质因子越小越好），所以答案：

\prod i = 1 k p i （ 总 值 \leq n ）

$\prod_{i=1}^kpi（总值\leq n）$
然后看数据，压位高精吧

#include <iostream>
#include <cstdio>
#include <cstring>
#define rep(i,a,b) for (i=a;i<=b;i++)
typedef long long ll;
const ll MOD=1e11;
using namespace std;
bool b[60001];
int a[6501],sop;
ll c[6501][2501],p[2501];
int t;
char n[25001];void Prime() {int i,cn;rep(i,2,60000)if (!b[i]) {a[++sop]=i;cn=2*i;while (cn<=60000) {b[cn]=1;cn+=i;}}
}void Multi(int a,int b,int key) {int i,j;rep(i,1,c[a][0]) {c[b][i]+=c[a][i]*key;c[b][i+1]+=c[b][i]/MOD;c[b][i]=c[b][i]%MOD;}c[b][0]=c[a][0];if (c[b][c[b][0]+1]) c[b][0]++;
}bool Judge(ll *a,ll *b) {int i;if (a[0]<b[0]) return 1;if (a[0]>b[0]) return 0;for (i=a[0];i;i--)if (a[i]>b[i]) return 0; else if (a[i]<b[i]) return 1;return 0;
}int main() {int i,j;Prime();c[0][0]=c[0][1]=1;rep(i,1,sop)Multi(i-1,i,a[i]);scanf("%d",&t);while (t--) {scanf("%s",&n);p[0]=0;ll w=1,num=0;int len=strlen(n);rep(i,0,len-1) {num+=w*(n[len-i-1]-'0');w*=10;if (w==MOD) {p[++p[0]]=num;w=1;num=0;}}if (num) p[++p[0]]=num;rep(i,1,sop)if (Judge(p,c[i])) {printf("%lld",c[i-1][c[i-1][0]]);for (j=c[i-1][0]-1;j;j--)printf("%011lld",c[i-1][j]);printf("\n");break;}}
}