Description
Consider the fraction, n/d, where n and d are positive integers. If n <= d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d <= x?
Input
The input will consist of a series of x, 1 < x < 1000001.
Output
For each input integer x, you should output the number of elements contained in the set of reduced proper fractions for d <= x in one line.
Sample Input
3
8
Sample Output
3
21
Hint
HCF代表最大公約數(shù)
這里主要說(shuō)一下素?cái)?shù)篩法，該方法可以快速的選取出1~N數(shù)字中的所有素?cái)?shù)。時(shí)間復(fù)雜度遠(yuǎn)小于O(N*sqrt(N))
方法為：從2開(kāi)始，往后所有素?cái)?shù)的倍數(shù)都不是素?cái)?shù)。最后剩下的數(shù)都是素?cái)?shù)。
再說(shuō)說(shuō)歐拉公式，用來(lái)解決所有小于n中的數(shù)字有多少個(gè)與n互質(zhì)，用Ψ(n)表示。
Ψ(n)=n*(1-1/q1)*(1-1/q2)*……*(1-1/qk),n為和數(shù)，其中qi為n的質(zhì)因數(shù)。
Ψ(n)=n-1，n為質(zhì)數(shù)
注意：關(guān)于數(shù)論的題很容易超過(guò)int類型的范圍，多考慮用long long類型。
歐拉函數(shù)請(qǐng)參閱：
http://zh.wikipedia.org/zh-cn/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0
代碼
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LEN 1100010
using namespace std;
int len0 = (int)sqrt(LEN);
int isp[LEN];//isprime?
int pr[LEN];//依次記錄素?cái)?shù)
int pct;// prime count
long long rs[LEN];//fi(n)
int main()
{
int i, j;
int x;
memset(isp, -1, sizeof(isp));
for(int i = 2; i <= len0; i++)//素?cái)?shù)篩法選出素?cái)?shù)
{
if(isp[i])
{
for(int j = i * 2; j < LEN; j += i)
isp[j] = 0;
}
}
pct = 0;
for(int i = 2; i < LEN; i++)//記下選出的素?cái)?shù)
if(isp[i])
pr[pct++] = i;
for(int i = 0; i < LEN; i++)
rs[i] = i;
for(int i = 0; i < pct; i++)
{
rs[pr[i]]--;
for(int j = pr[i] * 2; j < LEN; j += pr[i])
{
rs[j] = rs[j] / pr[i] * (pr[i] - 1);//rs[]要定義成long long類型，因?yàn)橛?jì)算過(guò)程中乘法會(huì)超過(guò)int類型的取值范圍
//rs[j] -= rs[j] / pr[i];
}
}
while(scanf("%d", &x) != EOF)
{
long long sum = 0;
for(int i = 2; i <= x; i++)
sum += rs[i];
//printf("%lld\n", sum);
cout << sum << endl;//用cout輸出，不用考慮使用%lld還是%I64d
}
//system("pause");
return 0;
}
posted on 2013-04-30 21:26
小鼠標(biāo) 閱讀(1310)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
數(shù)論