ACM

2024-07-11 02:44| 来源: 网络整理| 查看: 265

目录：整除的性质常见定理模与余 3.1模运算 3.2同余的性质 3.3快速幂数论重要定理及应用 4.1欧几里得定理 4.2扩展欧几里得 4.3线性同余方程(模线性方程) 4.4中国剩余定理(模线性方程组) 4.5乘法逆元 4.6二次同余方程 4.7唯一分解定理素数及其相关定理 5.1反素数 5.2素数筛 5.3素性测试 5.4欧拉函数 5.5欧拉降幂公式 5.6积性函数莫比乌斯相关 6.1莫比乌斯函数 6.2莫比乌斯反演逆序数原根离散对数一.整除的性质：

1.若a|b -a|b a|-b |a| | |b| 2.若a|b，b|c -> a|c 3.若a|b，a|c -> a|(bx+cy) 其中x，y为任意整数 4.若a|b -> am|bm 其中m为非零整数 5.若a|b，b|a -> b=±a |b|=|a| 6.若a|bc，且a与c互质，则a|b 7.若a|b，a|c，且b与c互质，则a|bc 8.若a|b，c为任意整数，则b|ac 9.对任意整数a，b>0，存在唯一的数对q，r，使a=bq+r，其中0≤r if(n & 1) ans = ans * a % p; //若不取模就去掉p a = a * a % p; n >>= 1; } return ans; } 3.2大数快速幂：n>long long (该版本不稳定，建议使用优化版本) typedef unsigned long long LL; string str; int input[10000005]; int output[10000005]; int len; int sum=1,d=0,k=0; void to_bin(string str) //将大整数转换为二进制，转换后为逆序 { len=str.size(); for(int i=0;i d = input[i] / 2; sum += d; if(i == (len - 1)){ output[k++] = input[i] % 2; } else input[i+1] += (input[i]%2)*10; input[i] = d; } } } LL pow(LL a, int n[], LL p) //快速幂 a^n % p { LL ans = 1; int i=0; while(i LL a,b,c; while(cin>>a>>str>>c) { to_bin(str); cout if(b&1){ ans=(ans*a)%mod; b--; } b/=2; a=a*a%mod; } return ans; }//内部也用快速幂 long long quickmod(long long a,char *b,int len) { long long ans=1; while(len>0){ if(b[len-1]!='0'){ int s=b[len-1]-'0'; ans=ans*quick_mod(a,s)%mod; } a=quick_mod(a,10)%mod; len--; } return ans; } int main(){ char s[100050]; int a; while(~scanf("%d",&a)) //求a^s%mod { scanf("%s",s); int len=strlen(s); printf("%I64d\n",quickmod(a,s,len)); } return 0; } 四.数论重要定理及应用 1.欧几里得定理 1.1定义：

gcd(a,b)=gcd(b,a%b)

1.2最大公约数与最小公倍数 int gcd(int a,int b) //最大公约数 { if(b==0) return a; else return gcd(b,a%b); } int lcm(int a,int b) //最小公倍数 { return a/gcd(a,b)*b; //防止溢出 } 2.扩展欧几里得 2.1定义：

ax+by=gcd(a,b)=d，在已知a,b的情况下求解出一组x,y

2.2推导过程：

因为a%b=a-(a/b)b 则有 d=bx1+[a-(a/b)b]y1=bx1+ay1-(a/b)by1=ay1+b(x1-a/by1) 故 x=y1,y=x1-a/by1

2.3性质：

1.若通过扩展欧几里得求出一组特解(x0,y0)，那么有ax0+by0=d. 则方程的通解为，其中k为任意整数 x=x0+k*(b/d) y=y0-k*(a/d) 2.已知ax+by=d的解，对于ax+by=c的解，c为任意正整数，只有当d|c时才有解其通解为 x=(c/d)x0+k(b/d) y=(c/d)y0-k(a/d)

2.4常见用法：

（1）求形如ax+by=c的通解，或从中选取某些特解（2）求乘法逆元（3）求解线性同余方程

int exgcd(int a, int b, int &x, int &y) { //x，y初始为任意值，最后变为一组特解 if(b == 0) { //对应最终情况，a=gcd(a,b),b=0,此时x=1，y为任意数 x = 1; y = 0; return a; } int r = exgcd(b, a % b, x, y); //先递归到最终情况，再反推出初始情况 int t = x; x = y; y = t - a / b * y; return r; //gcd(a,b) } 3.线性同余方程(模线性方程) 3.1定义：

形如：ax≡b (mod n)的方程。

3.2性质

定理1：此方程对于未知量x有解当且仅当 gcd(a,n) | b 定理2：d=gcd(a,n)，若d|b，则方程恰好有d个模n不同余的解，否则方程无解定理3：若x0是方程的任一解，则该方程对模n有d个不同的解，分别为xi=x0+k*(b/d),(k=1,2,…,d-1)

3.3解线性同余方程：

ax≡b (mod n) —> ax+ny=b d=gcd(a,n)，若不满足d|b，则方程无解否则, ax0+ny0=d，利用扩展欧几里得求出一组特解(x0,y0) 然后，x=x0*(b/d)%n就是原方程的一个解且其有d个不同的解，为xi=(x+k*(b/d))%n，0 X = X * (b / d) % n;//得到同于方程一解 for(int i = 0 ; i printf("No Sulutions!\n"); } } 4.中国剩余定理(模线性方程组) 4.1定义：

对于模线性方程组这里写图片描述

4.2常规中国剩余定理：各m互质时 int CRT(int a[], int m[], int n) { int M = 1; int ans = 0; for(int i = 1; i int x, y; int Mi = M / m[i]; exgcd(Mi, m[i], x, y); ans = (ans + Mi * x * a[i]) % M; } if(ans x=1,y=0;return a;} LL re=exgcd(b,a%b,x,y),tmp=x; x=y,y=tmp-(a/b)*y; return re; } LL m[maxn],a[maxn]; //m为模数集，a为余数集 LL exCRT(){ LL M=m[1],A=a[1],t,d,x,y;int i; for(i=2;i int i,j; while(scanf("%d",&n)!=EOF){ for(i=1;i if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b>>=1; } return ans; } LL exgcd(LL a,LL b,LL &x,LL &y) //扩展欧几里得 { if(!b) { x=1; y=0; return a; } LL GCD=exgcd(b,a%b,x,y); LL tmp=x; x=y; y=tmp-a/b*y; return GCD; } LL inv1(LL a,LL mod)//扩展欧几里得求逆元 { LL x,y; LL d=exgcd(a,mod,x,y); if(d==1) return (x%mod+mod)%mod; return -1; } LL inv2(LL a,LL mod)//费马小定理 { return ksm(a,mod-2,mod); } void inv3(LL mod)//线性递推求1~n的所以逆元 { inv[1]=1; for(int i=2;i LL n,mod; while(cin>>n>>mod) { cout if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; } LL p; LL w;//二次域的D值 bool ok;//是否有解 struct QuadraticField//二次域 { LL x, y; QuadraticField operator*(QuadraticField T)//二次域乘法重载 { QuadraticField ans; ans.x = (this->x*T.x%p + this->y*T.y%p*w%p) % p; ans.y = (this->x*T.y%p + this->y*T.x%p) % p; return ans; } QuadraticField operator^(LL b)//二次域快速幂 { QuadraticField ans; QuadraticField a = *this; ans.x = 1; ans.y = 0; while (b) { if (b & 1) { ans = ans*a; b--; } b /= 2; a = a*a; } return ans; } }; LL Legender(LL a)//求勒让德符号 { LL ans=quick_mod(a, (p - 1) / 2, p); if (ans + 1 == p)//如果ans的值为-1，%p之后会变成p-1。 return -1; else return ans; } LL Getw(LL n, LL a)//根据随机出来a的值确定对应w的值 { return ((a*a - n) % p + p) % p;//防爆处理 } LL Solve(LL n) { LL a; if (p == 2)//当p为2的时候，n只会是0或1，然后0和1就是对应的解 return n; if (Legender(n) == -1)//无解 ok = false; srand((unsigned)time(NULL)); while (1)//随机a的值直到有解 { a = random(0, p - 1); w = Getw(n, a); if (Legender(w) == -1) break; } QuadraticField ans,res; res.x = a; res.y = 1;//res的值就是a+根号w ans = res ^ ((p + 1) / 2); return ans.x; } int main() { LL n,ans1,ans2; while (scanf("%lld%lld",&n,&p)!=EOF) { ok = true; n %= p; ans1 = Solve(n); ans2 = p - ans1;//一组解的和是p if (!ok) { printf("No root\n"); continue; } if (ans1 == ans2) printf("%lld\n", ans1); else printf("%lld %lld\n", ans1, ans2); } } 7.唯一分解定理： 7.1定义：

任何一个大于1的自然数 N ，都可以唯一分解成有限个质数的乘积，这里均为质数，其诸指数是正整数。

7.2性质：

1.重要推理：如果质数p是ab的因子，那么p或者是a的因子，或者是b的因子 2.N的因子个数为：这里写图片描述 3.N的全体正因数之和为：

7.3唯一分解定理完全模板：O(φ(n)) #include using namespace std; typedef long long LL; const int mod=1e9+7; bool check[100005]; int prime[100005]; //储存第i个素数 int tot=0; LL pow(LL a, LL n, LL p) //快速幂 a^n % p { LL ans = 1; while(n) { if(n & 1) ans = ans * a % p; //若不取模就去掉p a = a * a % p; n >>= 1; } return ans; } void getprime(int n) { memset(check, 0, sizeof(check)); // 标记数组初始化，初始均为 0 tot = 0; // tot 初始为 0，用来记录质数总个数 for (int i = 2; i // 如果 i 没有被划去，则 i 为质数，加入质数表中 prime[++tot] = i; } for (int j = 1; j // 判断合数是否在区间内 break; } check[i * prime[j]] = 1; // 划去在区间内的合数 if (i % prime[j] == 0) { // 保证合数只被其最小的质因子划去，提高筛选效率 break; } } } } void getans(int n) { int a[10000],b[100005],c[100005],cnt=0,cnt2=0,t; t=n; for(int i=1;prime[i]*prime[i] a[cnt]=prime[i]; while(n%prime[i]==0) { c[cnt2++]=prime[i]; b[cnt]++; n/=prime[i]; } cnt++; } } if(n!=1) { a[cnt]=n; b[cnt]=1; c[cnt2]=n; cnt2++; cnt++; } int cnt_factor=1; //因数的个数 long long sum_factor=1; //全部因数之和 for(int i=0;i cur+=pow(a[i],j,mod); } sum_factor*=cur; } cout cnt=0; memset(is,1,sizeof(is)); memset(ans,0,sizeof(ans)); memset(prime,0,sizeof(prime)); for(int i=2;i prime[cnt++]=i; for(int j=i+i;j int n; while(~scanf("%d",&n)){ init(n); for(int i=0;i if(b&1){ret+=a;ret%=c;} a>=1; } return ret; } //计算 x^n %c long long pow_mod(long long x,long long n,long long mod)//x^n%c { if(n==1)return x%mod; x%=mod; long long tmp=x; long long ret=1; while(n) { if(n&1) ret=mult_mod(ret,tmp,mod); tmp=mult_mod(tmp,tmp,mod); n>>=1; } return ret; } //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数 //一定是合数返回true,不一定返回false bool check(long long a,long long n,long long x,long long t) { long long ret=pow_mod(a,x,n); long long last=ret; for(int i=1;i if(n long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件 if(check(a,n,x,t)) return false;//合数 } return true; } //************************************************ //pollard_rho 算法进行质因数分解 //************************************************ long long factor[100];//质因数分解结果（刚返回时是无序的） int tol;//质因数的个数。数组小标从0开始 long long gcd(long long a,long long b) { if(a==0)return 1;//??????? if(a long long i=1,k=2; long long x0=rand()%x; long long y=x0; while(1) { i++; x0=(mult_mod(x0,x0,x)+c)%x; long long d=gcd(y-x0,x); if(d!=1&&d!=x) return d; if(y==x0) return x; if(i==k){y=x0;k+=k;} } } //对n进行素因子分解 void findfac(long long n) { if(Miller_Rabin(n))//素数 { factor[tol++]=n; return; } long long p=n; while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p); } int main() { //srand(time(NULL));//需要time.h头文件//POJ上G++不能加这句话 long long n; while(scanf("%I64d",&n)!=EOF) { tol=0; findfac(n); for(int i=0;ig(i) 0 < i < x，则称x为反质数。例如，整数1，2，4，6等都是反质数。即是区间中约数最多的那个数

1.2性质：

1.一个反素数的质因子必然是从2开始连续的质数 2.N=p1^a1 *p2^a2 *…*pn^an，必然有a1>=a2>=a3…>=an

1.3常见用法：

（1）给定一个数N，求一个最小的正整数X，使得X的约数个数为N

#include #define inf (0x3f3f3f3f) typedef long long int LL; LL pr, mx, BEGIN, END = 1e18; const int maxn=50+20; int prime[maxn];//这个记得用int，他保存的是质数，可以不用开maxn那么大 bool check[maxn]; int total; int n; void initprime() { for (int i=2; i //是质数了 prime[++total]=i;//只能这样记录，因为后面要用 } for (int j=1; j if (depth > total) return ; // 越界了，用不到那么多素数 if ((cnt > mx || cnt == mx && pr > curnum) && cnt == n) { pr = curnum; mx = cnt; } for (int i = 1; i cin >> n; dfs(1, 1, 1, 64); cout for (int i=2; i prime[++total]=i; } for (int j=1; j if (depth > total) return ; // if ((cnt > mx || cnt == mx && pr > curnum) && curnum >= BEGIN) { pr = curnum; mx = cnt; } for (int i = 1; i pr = 0, mx = 0, BEGIN = 1; cin >> END; dfs(1, 1, 1, 64); cout work(); } return 0; }

（3）求[begin,end]中最小的反素数：

#include using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; LL pr, mx, BEGIN, END = 1e18; const int maxn=1e6+20; int prime[maxn];//这个记得用int，他保存的是质数，可以不用开maxn那么大 bool check[maxn]; int total; int n; void initprime() { for (int i=2; i //是质数了 prime[++total]=i;//只能这样记录，因为后面要用 } for (int j=1; j LL ans = 1; while (b) { if (b & 1) { ans *= a; } a *= a; b >>= 1; } return ans; } void dfs (int cur,int cnt,LL now,LL from) { LL t=from*(cnt+1);//现在一共拥有的因子数 if (now>=BEGIN && t>mx || t==mx && pr>now && now >= BEGIN) { //有得换了 mx=t; pr=now; } for (int i=cur; i //没有变，一直都是用这个数.2^k dfs(cur,cnt+1,temp,from);//唯一就是from没变，一直都是用着2，不是新质数 } else { //枚举新质数了。 LL k = (cnt+1)*from; //现在有K个因子 LL q=(LL)(log(END/now) / log(prime[cur])); //2*3插入5时，用的是3来放缩 LL add = k*mypow(2,q); if (add prime[total]) { //试着给他乘上一个大素数 [999991,999991] if ( k*2 > mx ) { //乘以一个大素数，因子数*2 pr = END;//如果只有一个大素数[1e9+7,le9+7]那么，就是端点值 //否则，是2*3*5*bigprime的话，结果不是最优的， mx = k*2; } } dfs(i,1,temp,k); } } return; } void work() { cin >> BEGIN >> END; dfs(1,0,1,1); cout memset(check, 0, sizeof(check)); // 标记数组初始化，初始均为 0 int tot = 0; // tot 初始为 0，用来记录质数总个数 for (int i = 2; i // 如果 i 没有被划去，则 i 为质数，加入质数表中 prime[++tot] = i; } for (int j = 1; j // 判断合数是否在区间内 break; } check[i * prime[j]] = 1; // 划去在区间内的合数 if (i % prime[j] == 0) { // 保证合数只被其最小的质因子划去，提高筛选效率 break; } } } 2.2埃氏素数筛：O(nloglogn) vectorprime; //其中存储2-n的所有素数 bool is_prime[MAXN] //存储第i项是否为素数 void find_prime(int n) { int p=0; for(int i=2;i prime.push_back(i); for(int j=2*i;j if(b&1){ret+=a;ret%=c;} a>=1; } return ret; } //计算 x^n %c long long pow_mod(long long x,long long n,long long mod)//x^n%c { if(n==1)return x%mod; x%=mod; long long tmp=x; long long ret=1; while(n) { if(n&1) ret=mult_mod(ret,tmp,mod); tmp=mult_mod(tmp,tmp,mod); n>>=1; } return ret; } //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数 //一定是合数返回true,不一定返回false bool check(long long a,long long n,long long x,long long t) { long long ret=pow_mod(a,x,n); long long last=ret; for(int i=1;i if(n long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件 if(check(a,n,x,t)) return false;//合数 } return true; } int main() { long long n; while(scanf("%I64d",&n)!=EOF) { if(Miller_Rabin(n))printf("Yes\n"); else printf("No\n"); } return 0; } 4.欧拉函数： 4.1定义：

互质：gcd(a,b)=1，则a，b互质欧拉函数φ(n):小于等于n的所有数中与n互质数的个数

4.2性质：

1.对于质数p， φ( p) = p - 1。注意φ(1)=1 2. 若m,n互质，φ(mn)=φ(m)φ(n) 3. 当n为奇数时，φ(2n)=φ(n) 4.当n大于2时，所有φ(n)都是偶数 5.当n大于6时，所有φ(n)都是合数

6.欧拉定理：对于互质的正整数a和n，有a^φ(n) ≡ 1 mod n 7.费马小定理：若gcd(a,b)=1，则a^(p-1)=1 mod n 8.欧拉定理推论：小于等于n的数中，与n互质数的总和为：φ(n)*n/2 (n>1)

4.3求一个数的欧拉函数：O(sqrt(n)) //直接求解欧拉函数 int euler(int n){ //返回euler(n) int res=n,a=n; for(int i=2;i*i res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } 4.4求1~n每个数的欧拉函数：O(nlogn) void Init(){ euler[1]=1; for(int i=2;i if(a%i==0){ res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } ll fast_mod(ll x,ll n,ll Max) //快速幂 { ll res=1; while(n>0) { if(n & 1) res=(res*x)%Max; x=(x*x)%Max; n >>= 1; } return res; } ll func(ll n,ll m){ //循环求解 if(m==1) return 0; if(n ans=fast_mod(i,ans,m); } return ans; }else{ ll phi=euler(m); ll z=func(n-1,phi); ans=fast_mod(n,phi+z,m); } return ans; } void solve(){ //计算exponial（n） scanf("%lld%lld",&n,&m); printf("%lld\n",func(n,m)); } int main(){ solve(); return 0; } 6.积性函数 6.1定义：

积性函数：若gcd(a,b)=1，且满足f(ab)=f(a)f(b)，则称f(x)为积性函数完全积性函数：对于任意正整数a，b，都满足f(ab)=f(a)f(b)，则称f(x)为完全积性函数

6.2性质:

1.若f(n),g(n)均为积性函数，则函数h(n)=f(n)g(n)也是积性函数 2.若f(n)为积性函数，则函数也是积性函数，反之一样 3.任何积性函数都能应用线性筛，在O(n)时间内求出1~n项

六.莫比乌斯 1.莫比乌斯函数： 1.1定义：

这里写图片描述

1.2性质：

1.对于任意正整数n，∑(d|n) μ(d)=[n=1]。（[n=1]表示只有当n=1成立时，返回值为1；否则，值为0；(这个就是用μ是容斥系数的性质可以证明)(PS:这一条性质是莫比乌斯反演中最常用的) 2.对于任意正整数n，∑(d|n) μ(d)/d=ϕ(n)/n。（这个性质很奇妙，它把欧拉函数和莫比乌斯函数结合起来）

1.3求μ函数：O(n) void get_mu(int n) { mu[1]=1; for(int i=2;iprim[++cnt]=i;mu[i]=-1;} for(int j=1;j int val,pos; }a[100005]; int lowbit(int x) //求2^k { return x & -x; } long long getsum(int n) //区间查询，求a[1~n]的和 { long long res = 0; while(n>0) { res+=c[n]; n=n-lowbit(n); } return res; } int change(int x) //单点更新，将c[x]的值加1 { while(x if(a.val!=b.val) return a.val>b.val; return a.pos>b.pos; } int main() { std::ios::sync_with_stdio(false); while(cin>>n) { memset(c,0,sizeof(c)); for(int i=1;i change(a[i].pos); //修改最大数位置的值 cnt+=getsum(a[i].pos-1); //最大数位置之前的所有位置和，即区间求和，可知比当前数小的数有多少个 } cout if (!f[i]) { f[i] = 1; prime[pNum++] = i; } for (int j = 0; j break; } } } } LL getProduct(int a,int b,int P)//快速求次幂mod { LL ans = 1; LL tmp = a; while (b) { if (b&1) { ans = ans*tmp%P; } tmp = tmp*tmp%P; b>>=1; } return ans; } bool judge(int num)//求num的所有的质因子 { int elem[1000]; int elemNum = 0; int k = P - 1; for (int i = 0; i flag = true; k /= prime[i]; } if (flag) { elem[elemNum ++] = prime[i]; } if (k==1) { break; } if (k/prime[i] if (getProduct(num,(P-1)/elem[i],P) == 1) { flag = false; break; } } return flag; } int main() { getPrime(); while (cin >> P) { for (int i = 2;;++i) { if (judge(i)) { cout if(ret == b) return i; ret = (ret*a) % p; }//枚举比较小的i LL x,y,d, v = 1, cnt = 0; while((d = gcd(a, p)) != 1) { if(b % d) return -1; b /= d, p /= d; v = (v * (a/d)) % p; ++cnt; }//约分直到(a, p) == 1 map h; LL m = ceil(sqrt(p)), t = 1; for(LL i = 0; i d = extgcd(v, p, x, y); x = (x* (b/d) % p + p) % p; if(h.count(x)) return i*m + h[x] + cnt; v = (v*t) % p; } return -1; }

【本文地址】

公司简介

联系我们