目录
一． 二． 三． 四． 五． 六． 七．
目录......................................................................................................................... 1 扩展的欧几里德和不定方程的解 ..................................................................... 2 中国同余定理 ..................................................................................................... 3 原根 ..................................................................................................................... 5 积性函数 ............................................................................................................. 6 欧拉函数性质 ..................................................................................................... 7 线性求1-max的欧拉函数值 ............................................................................. 9 求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) ..... 10
1
一． 扩展的欧几里德和不定方程的解
解不定方程ax + by = n的步骤如下:
(1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1
(2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。
(3)根据扩展欧几里德定理，可得方程a'x + b'y = n'的所有整数解为： x = n'x0 + b't y = n'y0 - a't (t为整数)
这也就是方程ax + by = n的所有整数解
利用扩展的欧几里德算法，计算(a, b)和满足gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。因此可得： x = n/gcd * x0 + b/gcd * t y = n/gcd * y0 - a/gcd * t (t是整数)
int extend_Euclid(int a, int b, int &x, int &y) {
if (b == 0){ x = 1; y = 0; return a; }
int gcd= extend_Euclid ( b, a % b, x, y ); int temp = x; x = y;
y = temp - (a / b) * y; return gcd; }
2
二． 中国同余定理
Poj 2891
#include
__int64 GCD(__int64 i,__int64 j) {
if(j==0) return i; else
return GCD(j,i%j); }
__int64 extend_Euclid(__int64 a, __int64 b, __int64 &x, __int64 &y) {
if (b == 0){ x = 1; y = 0; return a; }
__int64 gcd= extend_Euclid ( b, a % b, x, y ); __int64 temp = x; x = y;
y = temp - (a / b) * y; return gcd; }
//只有两个式子的中国同余定理，return z=a*xx+x=b*yy+y; __int64 CRT_2(__int64 a,__int64 x,__int64 b,__int64 y) {
__int64 xx,yy,gcd;
gcd=extend_Euclid(a,b,xx,yy); __int64 c=y-x; while(c<0) c+=a; if(c%gcd!=0) return -1; xx*=c/gcd; yy*=c/gcd;
__int64 t=yy/(a/gcd); while(yy-t*(a/gcd)>0) t++;
while(yy-(t-1)*(a/gcd)<=0)
3
t--;
return (t*(a/gcd)-yy)*b+y; }
//chinese remainder theorem
//crt[i][0]存的是除数，crt[i][1]存的是余数,0<=i
__int64 m=crt[0][0]/GCD(crt[0][0],crt[1][0])*crt[1][0];
__int64 ans=CRT_2(crt[0][0],crt[0][1],crt[1][0],crt[1][1])%m; for(int i=2;i ans=CRT_2(m,ans,crt[i][0],crt[i][1]); m*=crt[i][0]/GCD(m,crt[i][0]); ans%=m; } return ans; } int main(void) { int n; __int64 a[10000][2]; while(scanf(\ for(int i=0;i scanf(\ if(n==1) printf(\ else printf(\ } return 0; } 4 三． 原根 Poj 1284 ans=φ（p-1）;//p是素数 设h为一整数，n为一正整数，（h，n）=k，适合h^k=1（mod n）的最小正整数k叫做h对n的次数。如果k=φ（n），则此时h被称为模n的原根。1773年，欧拉证明了素数P有原根。1785年，勒让德证明：设k|（p-1），恰有φ(k)个模p互不同余的数对模p的次数为k。 大家可以去搜索一下“二次剩余” p是奇素数,如果{x%p | 1 <= i <= p - 1} = {1,2,...,p-1},则称x是p的原根. 给出一个p,问它的原根有多少个. {xi%p | 1 <= i <= p - 1} = {1,2,...,p-1} 等价于 {xi%(p-1) | 1 <= i <= p - 1} = {0,1,2,...,p-2},即为(p-1)的完全剩余系 若x,x...x 2 (p-1) i 是(p-1)的完全剩余系, 根据定理,可以推出若gcd(x, p-1) = 1时, (1,x,...,x(p-2))也是(p-1)的完全剩余系 因为若x != x (mod p-1),那么x*x != x*x (mod p-1),与条件m矛盾,所以 x = x (mod p-1), 由此可以确定答案为EulerPhi(p-1) 有误之处请指出.. (拉格朗日四平方和定理) 每个自然数均可表示成4个平方数之和。3个平方数之和不能表示形式如4k(8n+ 7)的数。 如果在一个正整数的因数分解式中，没有一个数有形式如4k+3的质数次方，该正整数可以表示成两个平方数之和。 i j i j i j 5 四． 积性函数 在非数论的领域，积性函数指所有对于任何a,b都有性质f(ab)=f(a)f(b)的函数。 而本条目只讨论在数论中的积性函数。对于正整数n的一个算术函数 f(n)，当中f(1)=1且当a,b互质，f(ab)=f(a)f(b)，在数论上就称它为积性函数。若某算术函数f(n)符合f(1)=1，且就算a,b不互质，f(ab)=f(a)f(b)，则称它为完全积性的。 积性函数的值完全由质数的幂决定，这和算术基本定理有关。即是说，若将n表示成质因数分解式如 N=p1^a1*p2^a2..pk^ak 则 f(N)=f(p1^a1)*f(p2^a2)*…f(pk^ak) 若f为积性函数且f(p^n) = f(p)^n，则f为完全积性函数。 例子： φ(n) －欧拉φ函数，计算与n互质的正整数之数目 μ(n) －默比乌斯函数，关于非平方数的质因子数目 gcd(n,k) －最大公因数，当k固定的情况 d(n) －n的正因数数目 σ(n) －n的所有正因数之和 σk(n): 因数函数，n的所有正因数的k次幂之和，当中k可为任何复数。在特例中有： σ0(n) = d(n) 及 σ1(n) = σ(n) 1(n) －不变的函数，定义为 1(n)=1 （完全积性） Id(n) －单位函数，定义为 Id(n)=n （完全积性） Idk(n) －幂函数，对于任何复数、实数k，定义为Idk(n) = n^k （完全积性） Id0(n) = 1(n) 及 Id1(n) = Id(n) ε(n) －定义为：若n = 1，ε(n)=1；若n > 1，ε(n)=0。有时称为“对于狄利克雷卷积的乘法单位”（完全积性） (n/p) －勒让德符号，p是固定质数（完全积性） λ(n) －刘维尔函数，关于能整除n的质因子的数目 γ(n)，定义为γ(n)=(-1)^ω(n)，在此加性函数ω(n)是不同能整除n的质数的数目 所有狄利克雷特征均是完全积性的 加性函数： 在非数论的领域，加性函数指有对于任何a,b都有性质f(ab)=f(a)+f(b)的函数。 而本条目只讨论在数论中的加性函数。对于正整数n的一个算术函数f(n)，当中f(1)=1且当a,b互质，f(ab)=f(a)+f(b)，在数论上就称它为加性函数。若某算术函数f(n)就算a,b不互质，f(ab)=f(a)+f(b)，称它为完全加性的。 Ω(n)—n的所有质因子数目。特别的是因为1无任何质因子，Ω(1)=0。 ω(n)—n的相异质因子数目 a0(n)（或称sopfr(n)）—所有n的质因子之和 a1(n)（或称sopf(n)）—所有n的不同质因子之和 6 五． 欧拉函数性质 在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。 例如，因为1,3,5,7均和8互质。 欧拉函数实际上是模n的同余类所构成的乘法群（即环的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。 phi(n)<=n; phi(1)=1; phi(p)=p-1; phi(p^n)=(p-1)*p^(n-1); phi(m*n)=phi(m)*phi(n); gcd(n,m)=1; (m,k)=1, k^phi(m)=1(modm); Pku 2480 n f(n)??gcd(i,N) i?1 f(n)??d*?(n/d)d|n d Try to prove ： f(m*m')?f(m)*f(m') Euler递推式 若(N%a==0 && (N/a)%a==0) 则有: phi(n)=phi(n/a)*a; 若(N%a==0 && (N/a)%a!=0) 则有: phi(n)=phi(n/a)*(a-1); 7 若n=1 若n为无平方数因数的数，且n = p1p2......pk（k为因数个数） 若n有大于1的平方数因数 ，其中n > 0。 对整数n > 6，当n为质数时，显然有 。 。对于合数的n，则有： 8 六． 线性求1-max的欧拉函数值 Poj 2478 O(n)求素数，求欧拉函数（1-MAX） #include __int64 sum[MAX]; void phif(void) { for(int i=2;i for(int j=0;j phi[i*pri[j]]=phi[i]*pri[j]; break; } else phi[i*pri[j]]=phi[i]*phi[pri[j]]; } } } int main(void) { phif(); int n; sum[2]=phi[2]; for(int i=3;i<=1000000;i++) sum[i]=sum[i-1]+phi[i]; while(1){ scanf(\ if(n==0) break; printf(\ } return 0; } 9 七． 求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) Poj3358,求n/m表示成2进制小数的循环节起始位和长度。 #include for(int i=2;i<1000000;i++){ if(pp[i]==0){ p[pn++]=i; for(int j=i;i<1000&&i*j<1000000;j++) pp[i*j]=1; } } //printf(\} __int64 phif(__int64 n) { __int64 k=n; for(int i=0;i while(k%p[i]==0) k/=p[i]; } } if(k!=1) n-=n/k; return n; } __int64 pm[100]; //pm[i]=d^(1< __int64 pow_mod(__int64 d,__int64 k,__int64 m) { if(pm[0]==-1){ pm[0]=d%m; for(int i=1;i<100;i++) pm[i]=pm[i-1]*pm[i-1]%m; } __int64 n=1; 10 for(int i=0;k>0;i++){ if(k&1==1){ n*=pm[i]; n%=m; } k>>=1; } return n; } __int64 GCD(__int64 x,__int64 y) { if(x==0) return y; else return GCD(y%x,x); } int main(void) { pf(); int cas=1; __int64 k,n,m,ans0,ans1,phn; while(scanf(\ k=GCD(m,n); m/=k; n/=k; for(ans0=1;n%2==0;ans0++,n>>=1); m=phif(n); k=m; pm[0]=-1;//还原 for(int i=0;i while(k%p[i]==0) k/=p[i]; while(m%p[i]==0&&pow_mod(2,m/p[i],n)==1) m/=p[i]; } } printf(\ } system(\ return 0; } 11 语法：result=GCD(long long i,long long j); 参数： i,j 返回值： GCD(i,j) 注意： 源程序: long long GCD(long long i,long long j) { if(j==0) return i; else return GCD(j,i%j); } 语法：result=GCD(long long i,long long j); 参数： 求gcd(a,b)=ax+by，*x,*y 返回值： gcd(a,b),x,y 注意：*x,*y 源程序： long long Extend_Euclid(long long a,long long b,long long &x,long long &y) { if (b == 0){ x = 1; y = 0; return a; } long long gcd= Extend_Euclid ( b, a % b, x, y ); long long temp = x; x = y; 12 y = temp - (a / b) * y; return gcd; } 语法：result=China_Reminder_Therem(long long B[]],long long W[],long long n); 参数： B[]、W[]： a=B[] (mod W[]) 的对应参数,0<=i a 的值,如果没有解返回-1 注意： W[]存的是除数，B[]存的是余数,0<=i //其中W[],B[]已知，W[i]>0且W[i]与W[j]互质, 求a//?我也不清楚 源程序: long long GCD(long long i,long long j) { if(j==0) return i; else return GCD(j,i%j); } long long Extend_Euclid(long long a,long long b,long long &x,long long &y) { if (b == 0){ x = 1; y = 0; return a; } long long gcd= Extend_Euclid ( b, a % b, x, y ); long long temp = x; x = y; y = temp - (a / b) * y; 13 return gcd; } //只有两个式子的中国同余定理，return z=a*xx+x=b*yy+y; long long China_Reminder_Therem_2(long long a,long long x,long long b,long long y) { long long xx,yy,gcd; gcd=Extend_Euclid(a,b,xx,yy); long long c=y-x; while(c<0) c+=a; if(c%gcd!=0) return -1; xx*=c/gcd; yy*=c/gcd; long long t=yy/(a/gcd); while(yy-t*(a/gcd)>0) t++; while(yy-(t-1)*(a/gcd)<=0) t--; return (t*(a/gcd)-yy)*b+y; } long long China_Reminder_Theory(long long B[],long long W[],int n) { long long m=W[0]/GCD(W[0],W[1])*W[1]; long long ans=China_Reminder_Therem_2(W[0],W[0],W[1],B[1])%m; for(int i=2;i ans=China_Reminder_Therem_2(m,ans,crt[i][0],crt[i][1]); m*=W[i]/GCD(m,W[i]); ans%=m; } return ans; } 14