首页 > 其他 > 详细

Algorithm --> 求N以内的真分数个数

时间:2015-09-07 12:38:36      阅读:274      评论:0      收藏:0      [点我收藏+]

求N以内的真分数个数

For example, if N = 5, the number of possible irreducible fractions are 11 as below.

0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1

 

Input

1    --> case 个数
5

Output

11

 

代码:

#include <iostream>
#include <cstdio>

using namespace std;

#define _DEBUG 0
#define MAX 10001

int T, N;
int Answer;

int GCD(int a, int b)
{
    if(b == 0) return a;
    return GCD(b, a%b);
}

void _Count()
{
    for(int i = 1; i <= N; i++) {
        for(int j = 2; j <= N; j++) {
            if(i < j && GCD(i, j) == 1)
                Answer++;
        }
    }
}


int main()
{
    freopen("input_anirreduciblefraction.txt", "r", stdin);
    
    cin >> T;
    for(int tc = 0; tc < T; tc++) {

        Answer = 0;
        
        cin >> N;

        _Count();

        cout << Answer+2 << endl;
    }
}

 

输入文件:

5
1
2
4
7
10

 

Algorithm --> 求N以内的真分数个数

原文:http://www.cnblogs.com/jeakeven/p/4788357.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!