信息学竞赛中数论常见问题.doc

Prime概述:1的数,除了1和本身没有其他因子.1既不是素数也不是合数,0和所有的负整数同样如此.100以内的素数2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,971.打表(1)#define n 1000003int primen;/要判断的范围是多大,就要设置多大的数组,对应于某个数,看它下标对应的数是1，则是素数,否则,不是素数void getPrime() int i,j; int bound=sqrt(double)n); for(i=2;in;i+)primei=1;/将所有的数置1，表示这些数都是素数. for(i=2;ibound;i+)/注意从2开始 for(j=i+i;jn;j+=i)/将2的倍数置成0，表示不是素数 primej=0; 打表(2)int prim50,pn=0;bool pp101;void pre() int i,j; for (i=2;i=100;i+) if (!ppi) primpn+=i; for (j=0;jpn&i*primj=100;j+) ppprimj*i=1; if (i%primj=0) break; Pn是1至100范围内素数的个数,primi一次存放这pn个素数.这种方法的好处是存储素数时节省空间,输出素数时节省时间2. 直接判断bool isPrime2(int x) if(x=1)return false; if(x=2)return true; if(x%2=0)return false; double bound=sqrt(double)x); for(int i=3;i1,b1)1); else if (!(a&1)return kgcd(a1,b); else return kgcd(abs(a-b),min(a,b);LCM (最小公倍数)LCM ( a, b ) = a * b / GCD ( a, b ) 实际上最好写成a/GCD(a,b)*b long lcm(long a,long b) long c,d,sw; c=(a=b)?a:b; d=(a0?t:-t; e%=t; if(e0) e+=t; printf(%I64dn,e); 题目:1. /showproblem.php?pid=2669若n=p1e1p2e2prer，则 n的因数个数为 (1+e1)*(1+e2)*(1+er) n所有因数的和为(1+p1+p12+p1e1)*(1+p2+p22+p2e2) *(1+pr+pr2+prer)数的各位之和int sum( int number )int sum = 0;while( number != 0 ) sum += number % 10; number /= 10;return sum;/不知道数有几位,但是可以每次都取个位质因数分解对于i,从2到sqrt(double)m),如果m%i=0,则i是m的一个质因数,然后m/i=m,i=2,重新判断,直至最后,剩下的那个数同样是一个质因数,要加上的.int zhi(int n,int *x) int count=0; int i=2; while(i=(int)sqrt(double)n) if(n%i=0) xcount+=i; n=n/i; else i+; xcount+=n; return count;/返回质因数的个数,数组x是所有的因子/n是要分解的数,pn是100范围内质数的个数,prim是100范围内的所有质数,q存储分解出来的质数相应的个数int zhi_num(int n,int pn,int *prim,int *q) for (int j=0;jpn&primj=n;j+) if (n%primj=0) _int64 temp=0; while (n%primj=0) temp+;/相应的primj的个数 n/=primj; qj+=temp; 调用: prim25=2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97;int q25=0;int pn=25;zhi_num(20,pn,prim,q);欧拉函数欧拉函数值是小于或等于n的数中与n互质的数的个数 Phi(N)同样如此公式:(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4).(1-1/pn),其中p1, p2pn为x的所有质因数，x是不为0的整数。性质有:1. (1)=1（唯一和1互质的数就是1本身）。2. 若n是素数,则 (n)=n-1;3. 若n是合数,则 (n)n-1;4. 当n为奇数时，(2n)=(n),5. 若a,b互质,则, (a*b)=(a)*(b);代码:int euler(int x) int i,res=x; for(i=2;i1)res=res/x*(x-1); return res;中国剩余定理不管互质或者是不互质,只要在输入时进行互质处理,即可.而且,是_int64,显然通用性更强下面程序的输入输出格式:3/每组有几组数据3 2/除数 余数5 37 2#include using namespace std;_int64 x,y,t;_int64 extend_gcd(_int64 a,_int64 b) /return gcd(a,b) 得到x,y if(b = 0) x = 1; y = 0; return a; else _int64 temp = extend_gcd(b,a%b); t = x; x = y; y = t - a/b*y; return temp; int main() _int64 a1,a2,r1,r2,c,gcd,temp; bool yes; int n; freopen(G:/in.txt,r,stdin); while(scanf(%d,&n) !=EOF)/每组有一组数据 yes = false; scanf(%I64d %I64d,&a1 ,&r1);/a是除数,r是余数 for(int i=0 ;in-1 ;i+) scanf(%I64d %I64d,&a2 ,&r2); if(yes) continue; c = r2 - r1; gcd = extend_gcd(a1,a2); if(c%gcd != 0) yes = true; continue; temp = a2/gcd; x = (c/gcd*x % temp + temp)%temp; r1 = a1*x + r1; a1 = a1*a2/gcd; if(yes) printf(-1n); else printf(%I64dn,r1); return 0;闰年是否并返回一年天数/* 判断是否闰年 */bool isleap(int& year) if (year % 4 = 0 & year % 100 != 0 | year % 400 = 0) return true; else return false; /* 返回一年的最大天数 */int maxday(int& year) if (isleap(year) return 366; else return 365;Days是指距离某个日期是多少天,应该均可以的,只是最终结果可能有所变化的.string getweek(int& days) return weekdays % 7;一个关于日历的题目#include #include using namespace std; string week = Saturday, Sunday, Monday, Tuesday, Wednesday, Thursday, Friday;int day = 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31; /* 判断是否闰年 */bool isleap(int& year) if (year % 4 = 0 & year % 100 != 0 | year % 400 = 0) return true; else return false; /* 返回一年的最大天数 */int maxday(int& year) if (isleap(year) return 366; else return 365; /* 得到年份 */int getyear(int& days) int year = 2000; while (days maxday(year) days -= maxday(year); year+; return year; /* 得到月份 */int getmonth(int year, int& days) int month = 1; if (isleap(year) day2 = 29; else day2 = 28; while (days daymonth) days -= daymonth; month+; return month; /* 得到天数 */int getday(int& days) return days; /* 得到星期 */string getweek(int& days) return weekdays % 7; /* 主函数 */int main() int days; int y, m, d; string wk; while(cin days & days != -1) wk = getweek(days); days+; y = getyear(days); m = getmonth(y, days); d = getday(days); cout y -; if (m 10) cout 0; cout m -; if (d 10) cout 0; cout d wk endl; /system(pause); return 0;生成两个大的素数P,Q,乘起来得N=P*Q.然后算出N的欧拉函数Phi(N)=(P-1)*(Q-1).然后我们取一个范围在1,phi(N)中且与phi(N)互质的正整数E.它就是所谓的公钥。得到公钥之后，我们再算出E关于phi(N)的逆元D,即E*D mod phi(N)=1.这个D就是私钥。在得到这些数据以后，P,Q被丢弃，E,N做为公钥被公开，D做为私钥被解密人私人保存。假设有一个明文M,那么它所对应的密文就是C=ME mod N.如果我们现在得到一个密文C,那么它所对应的明文就是M=CD mod N也就是说，任何人都可以用公钥对数据进行加密，但是只有拥有私钥的人才可以对数据进行解密。将N分解成P*Q的乘积。那么就可以直接利用公式phi(N)=(P-1)*(Q-1)绕开暴力求解欧拉函数的过程，从而实现RSA的破解。这道题就是模拟这个破解过程，下面来说说具体的做法：1.首先用miller-rabin,pollard_rho做大整数的质因数分解，得到两个素数P,Q，pollard_rho的复杂度在N0.25次方，那么一个64位的整数 要计算的次数为 2640.25=216 =65536次，可以瞬间出解。2.求出phi(N)=(P-1)*(Q-1)3.然后用ext_gcd求出E关于phi(N)的逆元。4.用得到的私钥对数据C进行解密即可。PS:对这题而言，仅仅完成上述步骤还是不够的。因为N达到262次方，即使是使用无符号long long ,也很容易因为出乘法操作而溢出。这也是网上说要避免使用扩展欧几里德的原因。其实实现的时候，我们可以自己写一个特殊的乘法（内部用加法实现），由于使用的无符号的long long ，第64位刚好可以用来保存两个数加过之后的进位位，再模除又可以保证其在262范围内，即可避免溢出#include#include#include#include#includeusing namespace std;#define bigint _int64/这道题目不能用无符号数，不然wa/欧几里德，求最大公约数bigint gcd(bigint a,bigint b) while (b) bigint c = a % b; a = b; b = c; return a;/a*b%nbigint product_mod(bigint a,bigint b,bigint n) bigint tmp = 0; while (b) if (b&1) tmp += a; if (tmp=n) tmp-=n; a=n) a-=n; b=1; return tmp;/am%nbigint power_mod(bigint a,bigint m,bigint n) bigint tmp = 1; a%=n; while (m) if (m&1) tmp = product_mod(tmp,a,n); a = product_mod(a,a,n); m=1; return tmp;int pri = 2,3,5,7,11,13,17,19,23,29;/Miller_Rabin大素数判断bool Miller_Rabin(bigint n)/n,s.取s个随机数值a,进行a是n为和数的证明判断 if (n=1,k+; for (i = 0 ; i =n) return true; a = power_mod(prii,m,n);/幂取模 if (a=1) continue; for (j = 0 ; j 1 & D N) return D;/如果D不是非平凡因子 if (I = K) Y = X, K =N) T = pollard_rho(rand()%(N - 1) + 1,N); bigint A = rho(T); bigint B = rho(N / T); return AB?A:B;/扩展欧几里德，求ax+by=gcd(a,b)中的x，y，其中d=gcd(a,b)void Gcd(bigint a,bigint b,bigint &d,bigint