最简真分数

Problem Description

统计分母在指定区间[a,b]的最简真分数(分子小于分母，且分子分母无公因数)共有多少个，并求这些最简真分数的和（保留5位小数）。

Input

每行2个整数，分别表示a和b

Output

每行2个整数，分别表示最简真分数的个数和最简真分数的和

Sample Input

3 20

Sample Output

126 63.00000

解释：

这个题目，没有给定数据的范围，推测可能数据量不大，一般我们学校这种没有给定数据范围的题目，就暗示数据不大。按照常规思路。从a到b，开始遍历，然后遍历1..i，再看是不是最简真分数。

 1 /*
 2   
 3 */
 4 #include<bits/stdc++.h>
 5 
 6 using namespace std;
 7 const int N = 1000;
 8 
 9 double sum_nums[N];
10 int sums[N]; 
11 
12 int main(){
13     sum_nums[0] = sum_nums[1] = 0;
14     for (int i = 2; i < N; i++){
15         sum_nums[i] = sum_nums[i-1] + (double)1 / double(i);
16         sums[i] = sums[i-1] + 1; 
17         for (int x = 2; x < i; x++){
18             int flag = 0;
19             for (int t = 2; t <= x; t++){
20                 if (i % t == 0 && x % t == 0){
21                     flag = 1;
22                     break; 
23                 } 
24             } 
25             if (!flag) {
26                 sum_nums[i] += ((double)x / double(i)); 
27                 sums[i] ++; 
28             }
29         }
30     }
31     int a, b;
32     while (~scanf("%d %d", &a, &b))
33         printf("%d %.5lfn", sums[b]-sums[a-1], sum_nums[b] - sum_nums[a-1]); 
34     return 0;
35 }

View Code

这种数据数字的特征，与输入无关。例如 [1, 5] 的答案，不会因为你的输入时[1, 6]就会改变，一般采用打表记录的方式。

原文链接: https://www.cnblogs.com/gznb/p/11207022.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/299268

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

最简真分数

最简真分数

Problem Description

Input

Output

Sample Input

Sample Output

解释：

相关推荐