|
|
Euler's totient function 欧拉函数及其应用2008-11-02 20:08欧拉函数的定义:E(n)=([1,n-1]中与n互质的整数个数).因为任意正整数都可以唯一表示成如下形式:
k=p1^a1*p2^a2*……*pi^ai;(即分解质因数形式)
可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
=k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
=k*(1-1/p1)*(1-1/p2)....(1-1/pk)
在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素)
若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
应用如下例：
Farey Sequence
Time Limit: 1000MS
Description
The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
You task is to calculate the number of terms in the Farey sequence Fn.
Input
There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 106). There are no blank lines between cases. A line with a single 0 terminates the input.
Output
For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn.
Sample Input
2
3
4
5
0
Sample Output
1
3
5
9
题目意思就是计算小于或等于n的互质的对数，2 <= n <= 106,观察n的范围，如果用欧拉函数的话肯定会超时，这是要利用欧拉函数的性质了：
若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
这样在打出素数表后就可以直接计算每个数的的欧拉值了，最后累加起来就是小于或等于n的互质的对数了。核心代码如下，
void Prime2()
{
int num = 0, i, j, k;
for(i = 2; i < N; ++i)
{
if(!(a[i])) p[num++] = i;
for(j = 0; (j<num && i*p[j]<N); ++j)
{
k=i*p[j];
a[k] = 1;
factor[k]=p[j]; // 记录k的最小质因子
if(!(i%p[j])) break;
}
}
}
void phi()
{
int i, div;
for(i=2; i<N; i++)
{
if(a[i]==0)
f[i]=i-1;
else
{
div=i/factor[i];
if(div % factor[i]==0)
f[i]=f[div]*factor[i];
else
f[i]=f[div]*(factor[i]-1);
}
}
for(i=3; i<N; i++)
f[i]+=f[i-1];
}
其实这两个函数可以直接合并在一个函数里，下面是ac这道题的代码：
#include<cstdio>
#define N 1000001
bool a[N]={0};
int p[78498];
long long f[N];
void Prime_PHI()
{
int num = 0, i, j, k;
for(i = 2; i < N; ++i)
{
if(!(a[i]))
{
p[num++] = i;
f[i]=i-1;
}
for(j = 0; (j<num && (k=i*p[j])<N ); ++j)
{
a[k] = 1;
if(i%p[j]==0)
{
f[k]=f[i]*p[j];
break;
}
else
f[k]=f[i]*(p[j]-1);
}
}
for(i=3; i<N; i++)
f[i]+=f[i-1];
}
int main()
{
Prime_PHI();
int n;
while(scanf("%d",&n),n)
{
printf("%I64d\n", f[n]);
}
} |
|
楼主: 〇〇
IP卡
狗仔卡
楼主
显身卡
发表于 2010-11-9 23:14
发表于 2010-11-10 01:03
