最简分数_网易雷火笔试题

gywy

$欧拉函数\phi(n)表示小于n且与n互质的正整数的个数 \\ \phi(n)=n(1-\frac{1}{p_1})...(1-\frac{1}{p_k}) \\ n = p_1^{a_1}...p_k^{a_k} \\ p_1...p_k是质数$
直觉上看，n的质因子个数越多，这个比例越小。
其次，质因子越小，这个比例越小。
另外，因式分解中每个质因子的次数对欧拉函数没有影响。

因此，可以贪心来做，选择从2开始连续的质数，使得这些质数的乘积小于等于n。

（贪心的正确性暂时没有想出怎么证明）

#include <iostream>
using namespace std;
const int N = 100010;
bool st[N];
int primes[N], cnt, n;
int main() {
    scanf("%d", &n);
    for (int i = 2; i < N; i ++) {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] < N / i; j ++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
    int up = 1;
    int down = 1;
    for (int i = 0; i < cnt; i ++) {
        if ((long long)down * primes[i] <= n) down *= primes[i], up *= primes[i] - 1;
        else break;
    }
    double ratio = (double) up / (double) down;
    printf("%.6lf\n", ratio);
    return 0;
}

编辑于 2020-05-18 19:47:03 回复(0)

tentes

简单来说，质因子种类越多的数越可能产生非最简分数，从而使F(x)越小。因此，我们可以得到一串序列：1、2（1 * 2）、6（1*2*3）、30（1*2*3*5）……这些数就是对应范围内使得F(x)最小的数。本答案在本地事先计算出每一个数的F(x)值，存储在数组中并根据输入的n确定输出。

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int target[10] = {1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870};
    double result[10] = {1.000000, 0.500000, 0.333333, 0.266667, 0.228571, 0.207792, 0.191808, 0.180525, 0.171024, 0.163588};
    
    int i = 0;
    if (n >= target[9])
        cout << "0.163588" << endl;
    else
    {
        while (n >= target[i])
            i++;
        cout << setiosflags(ios::fixed) << fixed << setprecision(6) << result[i - 1] << endl;
    }
    
    return 0;
}

发表于 2021-03-31 14:24:10 回复(0)

在等offer的打工人很讲道理

你真牛逼

发表于 2021-03-30 19:25:02 回复(0)

Python

牛客444226503号

N = int(input())
p=[2,3,5,7,11,13,17,19,23,29,31]
facp=[1]
for i in range(len(p)):
    facp.append(p[i]*facp[-1])
res=1
for i in range(len(facp)-1,-1,-1):
    if N>=facp[i] and i>0:
        res=res*((p[i-1]-1)/p[i-1])
print("{:.6f}".format(res)+"\n")

编辑于 2024-02-22 17:25:00 回复(0)

你你你你你要跳舞吗

不管咋滴，都得指导欧拉函数，上面答案很妙，牛蛙。

发表于 2022-04-22 20:55:58 回复(0)

孙涌朝

import java.util.*;

public class Main
{
public static void main(String[] args)
{
int[] target = {1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870};
String[] result = {"1.000000", "0.500000", "0.333333", "0.266667", "0.228571", "0.207792", "0.191808", "0.180525", "0.171024", "0.163588"};

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 0; i < target.length;i++)
{
if(i != target.length-1)
{
if(n >= target[i] && n < target[i+1])
{
System.out.print(result[i]);
break;
}
}
else{
System.out.print(result[i]);
}

}
}
}

发表于 2022-03-25 14:18:54 回复(0)

最简分数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题