|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
bool Miller_Rabbin(int n,int a)//a属于[2,n） { if (n<2)return false; if (!(n%a))return false; int r=0,d=n-1; while (!(d&1)) { d>>=1; r++; } int k=pow_mod(a,d,n); if (k==1)return true; for (int i=0;i<r;i++) { if (k==n-1)return true; k=k*k%n; } return false; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
typedef long long qword; qword ext_gcd(qword a,qword b,qword &x,qword &y) { if (a%b==0) { //a*x+b*y==b x=0;y=1; return y; } qword ret=ext_gcd(b,a%b,x,y); qword tx=x,ty=y; x=ty; y=tx-a/b*ty; return ret; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include<iostream> using namespace std; #define MAXN 1010 bool pflag[MAXN]; int prime[MAXN],topp=-1; void init() { for (int i=2;i<MAXN;i++) { if (!pflag[i]) prime[++topp] = i; for (int j=0;j<=topp && prime[j]*i<MAXN;j++) { pflag[i*prime[j]] = true; if (i%prime[j] == 0)break; } } for (int i=0;i<=topp;i++) cout<<prime[i]<<endl; } int main() { init(); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<iostream> using namespace std; #define MAXN 100 #define MOD 1000000007 bool pflag[MAXN]; int prime[MAXN],topp=-1; int inv[MAXN]; int phi[MAXN]; int h[MAXN];//存最小的那个质数所在的括号 int hh[MAXN];//存其他括号的乘积 int g[MAXN];//存最小那个质数所在的括号有多少个数 int gg[MAXN];//存其他括号的个数的乘积 long long pow_mod(long long a,long long b) { long long res = 1; while (b) { if (b&1) res = res * a%MOD; a = a*a%MOD; b>>=1; } return res; } //(1+5+25)*(1+3) * (1+2) //(1+5+25)*(1+3) * (1+2+4) // hh[i] h[i] // //(1+2)*2+1 = (1+2+4) //(1+2+4)*2+1 = (1+2+4+8) // //(1+5+25) * (1+3) //(1+5+25)*(1+3) * (1+2) void init() { inv[1] = 1; for (int i=2;i<MAXN;i++) { if (!pflag[i]) { prime[++topp] = i; inv[i] = pow_mod(i,MOD-2); phi[i] = i-1; h[i] = i+1; hh[i] = 1; g[i] = 2; gg[i] = 1; } for (int j=0;j<=topp && i*prime[j]<MAXN;j++) { pflag[i*prime[j]] = true; inv[i*prime[j]] = (long long)inv[i] * inv[prime[j]] %MOD; if (i%prime[j] == 0) { phi[i*prime[j]] = phi[i] * prime[j]; h[i*prime[j]] = h[i] * prime[j] + 1; hh[i*prime[j]] = hh[i]; g[i*prime[j]] = g[i]+1; gg[i*prime[j]] = gg[i]; break; }else { phi[i*prime[j]] = phi[i] * (prime[j]-1); h[i*prime[j]] = prime[j] + 1; hh[i*prime[j]] = h[i] * hh[i]; g[i*prime[j]] = 2; gg[i*prime[j]] = g[i] * gg[i]; } } } } int main() { init(); /* for (int i=0;i<=topp;i++) cout<<prime[i]<<"\t";*/ for (int i=2;i<MAXN;i++) { cout<<i<<" INV="<<inv[i]<<" PHI="<<phi[i]<<" H="<<h[i]*hh[i]<<" G="<<g[i]*gg[i]<<endl; } } |