happy_lcj

题意：在第一象限中，格点（x,y）（0            已知数 n，求满足从（0,0）到（x,y）点,不经过其他任何格点的这样的点有多少个                                                      分析： F1：  (1,1)（0,1)（1,0)              F2： （0,1）  (1,1)  

原根定义：假设一个数g对于P来说是原根，那么g^i mod P的结果两两不同,          且有 1 简单来说，g^i mod p ≠ g^j mod p （p为素数） 其中i≠j且i, j介於1至(p-1)之间，则g为p的原根。 定理：如果为素数，那么素数一定存在原根，它恰有φ(φ(p))个不同的原根，              因为 p为素数，当然φ(p)=p-

欧拉函数是求小于x并且和x互质的数的个数 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn) 其中p1, p2……pn为x的所有质因数，x是不为0的整数 φ(1)=1（唯一和1互质的数就是1本身）【注意：每种质因数只一个。比如12=2*2*3】   定理：            （1）若n是素数p的k次幂，φ(n)=p^