拓展欧几里得公式： typedeflonglongLL;LLexgcd(LLa,LLb,LL&x,LL&y){if(a==0&&b==0)return-1;if(b==0){x=1;y=0;returna;}LLd=exgcd(b,a%b,y,x);y-=a/b*x;retur...

给定n,p求1~n中所有整数在模p意义下的乘法逆元。输入格式：一行n,p输出格式：n行,第i行表示i在模p意义下的逆元。输入输出样例输入样例#1： 1013输出样例#1： 179108112534说明1≤n≤3×106,n<p<20000528输入保证p为质数。首先我们来了解一下逆元。若...

http://poj.org/problem?id=3358（初始状态为分数形式）小数点进制转换原理：n/m;n/=gcd(n,m);m/=gcd(n,m);n=n%m;for(i:0to.....)n*=k;bit[i]=n/m;(保留每一位的数值）n%=m;题意：求n/m的小数点位的循环数列的长度和起始位置；现在假...

　　版权申明：本文为博主窗户(ColinCai)原创，欢迎转帖。如要转贴，必须注明原文网址　　http://www.cnblogs.com/Colin-Cai/p/7259802.html　　作者：窗户　　QQ：6679072　　E-mail：6679072@qq.com　　RSA是最常用的非对称加密算法。　　所谓非对...

　　求所有数x，满足x<n且x2≡1（mod n）。　　n<=2000000000 　　对于所有的数x，如果 x2 ≡1（mod n），　　那么有 x2 modn-1=0　　可以化为 (x+1)(x-1)...

 　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i)0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？（1<=N<=2,000,000,000...

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1222.html　　给定$a,b$，求$$sum_{n=a}^bsum_{i=1}^nsum_{j=1}^i[{mlcm}(i,j)=n]$$$$a,bleq10^{11}$$$${mTimeLimit}=6s$$　　本题...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ62.html太久没更博客了，该拯救我的博客了。$$sum_{1leqjleqn}gcd(i,j)^{c-d}i^dj^dx_j=b_i\A_i=i^dx_i,B_i=frac{b_i}{i^d},f(x)=x^{c-d}\f(...

注：转载本文须标明出处。原文链接https://www.cnblogs.com/zhouzhendong/p/Number-theory.html　　1.　基础回顾　　2.　中国剩余定理(CRT)及其扩展　　3.　卢卡斯定理(lucas)及其扩展　　4.　大步小步算法(BSGS) 及其扩展　　5.　原根与指标...

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1123.html　　$T$组数据。　　给定$A,B,C$，求出使得$x^AequivCpmodB$的所有$x$，保证解的个数不超过$sqrtB$。　　$Tleq100,1leqA,B,Cleq10^9$　　先记一下写这一题...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ2219.html　　求同余方程$x^AequivBpmod{C}$的解的个数，其中$C$为一个奇数。　　$1leqA,Bleq10^9,1leqlfloorC/2floorleq5imes10^8$  &...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ2480.html　　已知数$a,p,b$，求满足$a^x≡bpmodp$的最小自然数$x$。　　$a,p,bleq10^9$　　　ExBSGS模板题。   UPD(2018-09-1...

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1039.html 　　这题我用求高次剩余的做法，要卡常数。   UPD(2018-09-10): 　　详见数论总结。 　　传送门- https://ww...

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1038.html　　在模质数意义下，求高次剩余，模板题。   UPD(2018-09-10): 　　详见数论总结。 　　传送门- https://www.cnbl...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF1017F.html　　假设一个数$x$分解质因数后得到结果$x=p_1^{a_1}p_2^{a_2}cdotsp_k^{a_k}$　　定义$ext{exlog}_f(x)=a_1f(p_1)+a_2f(p_2)+...+a_kf...