频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
(Relax 数论1.9)POJ 3090 Visible Lattice Points(欧拉函数的应用:计算前n项欧拉数之和)
2013-11-21 16:26:13           
收藏   我要投稿
证明部分参考了https://blog.csdn.net/zhang20072844/article/details/8108727

看到这个题目简单分析了一下,最后才发现原来就是一个数论知识。

首先,题目主要是求从0,0能看到的点的个数。

先考虑只有1×1的时候,三个点,根据图明显看出,只需要计算下三角,结果=下三角的个数×2再加1(斜率为1的点)。

那么我们只需要计算斜率从0到1之间的个数就行了,不包括1,包括0.结果设为sum,那么最终就是2*sum+1.

 

1×1只有一个斜率为0的

2×2斜率有0,1/2(0已经算过了,以后不再算了),其实就多了一个斜率为1/2的。

3×3的时候,有1/3,2/3两个,比以前多了2个

4×4的时候,有1/4,2/4(1/2已经有过了),3/4,所以也是2个

5×5的时候,有1/5,2/5,3/5,4/5,之前都没有,所以多了4个

6×6得到时候,有1/6,2/6(1/3已经有了),3/6(1/2已经有了),4/6(2/3已经有了),5/6,所以只剩2个。

从上面可以发现一个规律,对于n×n,可以从0,0连接到(n,0)到(n,n)上,斜率将会是1/n,2/n......(n-1)/n;

凡是分子和分母能够约分的,也就是有公约数,前面都已经有过了。所以每次添加的个数就是分子和分母互质的个数。

 

那么问题就转换为,对于一个数n,求小于n的于n互质的数的个数,这不就是欧拉函数么?下面介绍欧拉函数。

转:

欧拉函数的定义:E(k)=([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)

     ps:在程序中利用欧拉函数如下性质,可以快速求出欧拉函数的值(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);

第一次写欧拉函数的题,琢磨的半天,最后还是只能按照最开始的想法写......

欧拉函数PHI(n)表示的是比n小,并且与n互质的正整数的个数(包括1)。比如:

PHI(1) = 1; PHI(2) = 1; PHI(3) = 2; PHI(4) = 2; ... PHI(9) = 6; ...

 

要计算一个正整数n的欧拉函数的方法如下:

1. 将n表示成素数的乘积: n = p1 ^ k1 * p2 ^ k2 * ... * pn ^ kn(这里p1, p2, ..., pn是素数)

2. PHI(n) = (p1 ^ k1 - p1 ^ (k1 - 1)) * (p2 ^ k2 - p2 ^ (k2 - 1)) * ... *(pn ^ kn - pn ^ (kn - 1))

              = Mult { pi ^ ki - pi ^ (ki -1) }

 

证明过程如下:

1. 容易想到:当n为素数时,PHI(n) = n - 1。因为每个比n小的正整数都和n互素。当n为素数p的k次方时,PHI(n) = p ^ k - p ^ (k - 1)。因为在1到n之间的正整数只有p的倍数和n不互素,这样的数有(p ^ k / p)个。

2. 如果m和n互素,即GCD(m, n) = 1,那么PHI(m * n) = PHI(m) * PHI(n)。用中国剩余定理可以证明,证明的思路是建立这样一种一一对应的关系(a, b) <-> x,其中正整数a小于m并且gcd(a, m) = 1,正整数b小于n并且gcd(b, n) = 1,正整数x小于m*n并且gcd(m*n, x) = 1。证明过程如下:

    1)根据中国剩余定理,如果m和n互素,那么关于未知量x的方程组x % m = a, x % n = b(0 <= a < m, 0 <= b < n),当0 <= x < m * n时存在并且仅存在一个解。容易证明,如果两个这样的方程组有相同的m, n但是a, b不同,那么他们的解x一定不同。

    2)首先用反正法证明:gcd(m, a) = 1且gcd(n, b) = 1是gcd(m*n, x) = 1的必要条件:假设gcd(a, m) = k > 1,由此可得:a = a' * k; m = m' * k => x = k' * m + a = k' * k * m' + k * a' = k * (k' * m' + a'); 所以gcd(x, m) = k > 1。同理可证,如果gcd(b, n) > 1, 那么gcd(x, n) > 1。所以x和m * n互素的必要条件是a和m互诉且b和n互素。

    3)接下来我们证明充分性:由x % m = a 可以得到x = k * m + a;由欧几里德算法求最大公约数的过程(就不证明了,呵呵,还得想)可以知道gcd(x, m) = gcd(m, a) = 1;同理可得,如果gcd(n, b) = 1那么gcd(x, n) = 1。接下来很容易得到:gcd(m*n, x) = 1。从而证明了充分性。

    4)上面三步的结论表明,数对(a, b)是可以和x建立起一一对应的关系的,所以有多少个不同的(a, b),就有多少个不同的x。

3.将n分解成素数乘积后,显然对于任意的i, j(i != j)都满足 pi ^ ki和pj ^ kj是互素的,于是可以的到上面的公式。

 

跟据上面的公式,可以得到关于欧拉函数的递推关系:

假设素数p能整除n,那么

如果p还能整除n / p, PHI(n) = PHI(n / p) * p;

如果p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);

 

 

 

#include <iostream>  
#include <cstdio>  
#include <cstring>  
  
using namespace std;  
  
typedef long long ll;  
  
const int maxn = 1000015;  
  
bool u[maxn];//判断某一个数是否是素数  
ll su[maxn];//素数表  
ll num = 0;//素数的个数  
ll phi[maxn];//phi[i]前i项欧拉数之和  
  
  
void prepare() { //欧拉筛法产生素数表  
    ll i, j;  
    memset(u, true, sizeof(u));  
  
    for (i = 2; i <= 1000010; ++i) {  
        if (u[i]) {  
            su[++num] = i;  
        }  
  
        for (j = 1; j <= num; ++j) {  
            if (i * su[j] > 1000010) {  
                break;  
            }  
  
            u[i * su[j]] = false;  
  
            if (i % su[j] == 0) {  
                break;  
            }  
        }  
    }  
}  
  
void geteuler() {//phi[i]前i项欧拉数的和...单纯用欧拉函数的模板,而不采用性质进行优化的话,和可能会TLE  
    int i;  
    phi[1] = 1;  
    for (i = 1; i <= 1000000; i++) {  
        int j;  
        for (j = 1; j <= num && su[j] * i <= 1000000; j++) {  
            /** 
             * 在这里需要利用两个性质。 
             * 第一,大于1的质数x的欧拉函数值为x-1,1的欧拉函数值为1。 
             * 第二,若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)。 
             * 
             */  
            if (i % su[j] == 0) {  
                phi[su[j] * i] = su[j] * phi[i];  
                break;  
            } else {  
                phi[su[j] * i] = phi[i] * (su[j] - 1);  
            }  
        }  
    }  
    for (i = 2; i <= 1000000; i++){//**这里是需要注意的地方...这里的i是从2开始算的,这个根据实际需要来,这是和POJ2478所不同的地方..  
        phi[i] += phi[i - 1];  
    }  
}  
  
  
int main(){  
    prepare();  
    geteuler();  
  
    int t;  
    scanf("%d",&t);  
  
    int counter = 1;  
    while(t--){  
        int n;  
        scanf("%d",&n);  
  
        printf("%d %d %lld\n",counter++,n,phi[n]*2+1);  
    }  
  
    return 0;  
}  

 

 

点击复制链接 与好友分享!回本站首页
上一篇:gpedit.msc(组策略)报错{8FC0B734-A0E1-11D1-A7D3-0000F87571E3}解决方法
下一篇:CodeForces 364A Matrix
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站