《ACM数论模板》由会员分享，可在线阅读，更多相关《ACM数论模板（9页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑ACM数论模板 目次 一 二 三 四 五 六 七 目次. 1 扩展的欧几里德和不定方程的解 . 2 中国同余定理 . 3 原根 . 5 积性函数 . 6 欧拉函数性质 . 7 线性求1-max的欧拉函数值 . 9 求单个欧拉函数，求最小的x(phi（n）%x=0),使得2x =1(mod n) . 10 1 一 扩展的欧几里德和不定方程的解 解不定方程ax + by = n的步骤如下: (1)计算gcd(a, b). 若gcd(a, b)不能整除n，那么方程无整数解；否那么，在方程的两边同除以gcd(a, b)，得到新的不定方程ax + by = n，此时g
2、cd(a, b) = 1 (2)求出不定方程ax + by = 1的一组整数解x0, y0，那么nx0，ny0是方程ax + by = n的一组整数解。 (3)根据扩展欧几里德定理，可得方程ax + by = n的全体整数解为： x = nx0 + bt y = ny0 - at (t为整数) 这也就是方程ax + by = n的全体整数解 利用扩展的欧几里德算法，计算(a, b)和得志gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了得志ax0 + by0 = 1的一组整数解。因此可得： x = n/gcd * x0 + b/gcd * t y = n/gcd * y
3、0 - a/gcd * t (t是整数) int extend_Euclid(int a, int b, int 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 #include using namespace std; _int64 GCD(_int64 i,_int64 j) if(j=0) return i; else return GCD(j,i
4、%j); _int64 extend_Euclid(_int64 a, _int64 b, _int64 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
5、(a,b,xx,yy); _int64 c=y-x; while(c0) t+; while(yy-(t-1)*(a/gcd)1,返回结果,-1表示无解 _int64 CRT(_int64 crt2,int n) _int64 m=crt00/GCD(crt00,crt10)*crt10; _int64 ans=CRT_2(crt00,crt01,crt10,crt11)%m; for(int i=2;i 1，(n)=0。有时称为“对于狄利克雷卷积的乘法单位”（完全积性） (n/p) 勒让德符号，p是固定质数（完全积性） (n) 刘维尔函数，关于能整除n的质因子的数目 (n)，定义为(n)=(
6、-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
7、)（或称sopf(n)）全体n的不同质因子之和 6 五 欧拉函数性质 在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为函数、欧拉商数等。 例如，由于1,3,5,7均和8互质。 欧拉函数实际上是模n的同余类所构成的乘法群（即环的全体单位元组成的乘法群）的阶。这天性质与拉格朗日定理一起构成了欧拉定理的证明。 phi(n) 0。 对整数n 6，当n为质数时，鲜明有 。 。对于合数的n，那么有： 8 六 线性求1-max的欧拉函数值 Poj 2478 O(n)求素数，求欧拉函数（1-MAX） #include using namespac
8、e std; const int MAX=1001000; int priMAX/3,pn=0; char notpMAX=0; int phiMAX; _int64 sumMAX; void phif(void) for(int i=2;i using namespace std; int p100000,pn=0; char pp1000000=0; void pf(void) for(int i=2;i0;i+) if(k n%=m; k=1; return n; _int64 GCD(_int64 x,_int64 y) if(x=0) return y; else return GC
9、D(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; pm0=-1;/恢复 for(int i=0;i 1;i+) if(k%pi=0) while(k%pi=0) k/=pi; while(m%pi=0 printf( system( return 0; 11 语法：result=GCD(long long i,long long j); 参数：
10、 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 y = 0; return a; long long gcd= Extend_Euclid ( b, a % b, x,
