一道恶心题的流氓解法（HUD 4002 Find the maximum）

好恶心的题。。。。。

证明可以证出来。。。。

欧拉函数：φ(n) = n(1 - 1/p1)(1 - 1/p2)(1 - 1/p3)....

n/φ(n) = (p1/(p1 - 1)) (p2/(p2 - 1)) ....

要使n/φ(n)最大，因为p/(p - 1)随p的增大而减小，所以p应该尽可能的小，p/(p - 1) > 1所以p尽可能的多。。。

也就是说从最小的素数开始往后连乘枚举，找到比n小且离n最近的数。。。。

 不得不吐嘈的是，=, =！这个java不能交！比赛的时候能用，现在不能用了。.。。杭电你在卖萌吗？！

吐嘈完毕。。。

我很流氓的用java打了个前n的素数相乘的表。。。。

然后在c里边开数组存起来。。。然后跟输入的字符串n比较。。

打表:

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        int t, i, j;
        int N = 1000;
        BigInteger n, m, tmp, one;
        Scanner cin = new Scanner (System.in);
        
        one = BigInteger.ONE;
        boolean[] b= new boolean[N];
        int[] pri = new int[N];
        
        int num = 0;
        for(i = 0; i < N; ++i) b[i] = true;
        for(i = 2; i < N; ++i) {
            for(j = i*i; j < N; j += i)
                b[j] = false;
        }
        for(i = 2; i < N; ++i) {
            if(b[i])    {pri[num++] = i; }
        }
        n = cin.nextBigInteger();
        m = one;
        for(i = 0; i < num; ++i) {
            tmp = m.multiply(BigInteger.valueOf(pri[i]));
            m = tmp;
            System.out.println("\"" + m + "\"" + ",");
            if(tmp.compareTo(n) > 0)    break;
        }
    }
}

比较：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <ctime>
#include <queue>
#include <map>
#include <sstream>

#define CL(arr, val)    memset(arr, val, sizeof(arr))
#define REP(i, n)       for((i) = 0; (i) < (n); ++(i))
#define FOR(i, l, h)    for((i) = (l); (i) <= (h); ++(i))
#define FORD(i, h, l)   for((i) = (h); (i) >= (l); --(i))
#define L(x)    (x) << 1
#define R(x)    (x) << 1 | 1
#define MID(l, r)   (l + r) >> 1
#define Min(x, y)   x < y ? x : y
#define Max(x, y)   x < y ? y : x
#define E(x)    (1 << (x))

const int eps = 1e-6;
const int inf = ~0u>>2;
typedef long long LL;

using namespace std;

char st[55][300] = {
    "2",
    "6",
    "30",
    "210",
    "2310",
    "30030",
    "510510",
    "9699690",
    "223092870",
    "6469693230",
    "200560490130",
    "7420738134810",
    "304250263527210",
    "13082761331670030",
    "614889782588491410",
    "32589158477190044730",
    "1922760350154212639070",
    "117288381359406970983270",
    "7858321551080267055879090",
    "557940830126698960967415390",
    "40729680599249024150621323470",
    "3217644767340672907899084554130",
    "267064515689275851355624017992790",
    "23768741896345550770650537601358310",
    "2305567963945518424753102147331756070",
    "232862364358497360900063316880507363070",
    "23984823528925228172706521638692258396210",
    "2566376117594999414479597815340071648394470",
    "279734996817854936178276161872067809674997230",
    "31610054640417607788145206291543662493274686990",
    "4014476939333036189094441199026045136645885247730",
    "525896479052627740771371797072411912900610967452630",
    "72047817630210000485677936198920432067383702541010310",
    "10014646650599190067509233131649940057366334653200433090",
    "1492182350939279320058875736615841068547583863326864530410",
    "225319534991831177328890236228992001350685163362356544091910",
    "35375166993717494840635767087951744212057570647889977422429870",
    "5766152219975951659023630035336134306565384015606066319856068810",
    "962947420735983927056946215901134429196419130606213075415963491270",
    "166589903787325219380851695350896256250980509594874862046961683989710",
    "29819592777931214269172453467810429868925511217482600306406141434158090",
    "5397346292805549782720214077673687806275517530364350655459511599582614290",
    "1030893141925860008499560888835674370998623848299590975192766715520279329390",
    "198962376391690981640415251545285153602734402721821058212203976095413910572270",
    "39195588149163123383161804554421175259738677336198748467804183290796540382737190",
    "7799922041683461553249199106329813876687996789903550945093032474868511536164700810",
    "1645783550795210387735581011435590727981167322669649249414629852197255934130751870910",
    "367009731827331916465034565550136732339800312955331782619462457039988073311157667212930",
    "83311209124804345037562846379881038241134671040860314654617977748077292641632790457335110",
    "19078266889580195013601891820992757757219839668357012055907516904309700014933909014729740190",
    "4445236185272185438169240794291312557432222642727183809026451438704160103479600800432029464270",
    "1062411448280052319722448549835623701226301211611796930357321893850294264731624591303255041960530",
    "256041159035492609053110100510385311995538591998443060216114576417920917800321526504084465112487730",
    "64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230",
};

int main() {
    //freopen("data.in", "r", stdin);

    int t, i;
    char s[200];
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        int ls = strlen(s);
        for(i = 0; i < 54; ++i) {
            int lt = strlen(st[i]);
            if(lt > ls)  break;
            else if(lt < ls)    continue;
            if(strcmp(st[i], s) > 0)    break;
        }
        printf("%s\n", st[i-1]);
    }
    return 0;
}