数论部分讲稿

[pdf-embedder url=”https://mhy12345.xyz/wp-content/uploads/securepdfs/2018/07/数论-讲义.pdf” title=”数论 讲义v1.0″]

[pdf-embedder url=”https://mhy12345.xyz/wp-content/uploads/securepdfs/2018/07/数论-课件.pdf” title=”数论 课件 v1.0″]

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;
}

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;
}

#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();
}

 

#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;
	}
}