质数

唯一分解定理

分解质因数的依据 一个数能且只能分解为一组质数的乘积。可知，若输入的数满足题目条件，他就只能分解为两个质数的乘积。所以在比他小且大于1的自然数中，只有那两个数能整除它，之间不可能再有任何合数或质数能整除它了，因为最小的能整除它的合数已经是他本身了。

#include<iostream> using namespace std; int main() { int n; cin>>n;//分解n for(int i=2;i<=n;++i) if(n%i==0) { cout<<i<<" "<<(n/i); return 0; } }

最大公约数的运用

洛谷P2441 角色属性树

题目描述 绪萌同人社是一个有趣的组织，该组织结构是一个树形结构。有一个社长，直接下属一些副社长。每个副社长又直接下属一些部长……。

每个成员都有一个萌点的属性，萌点属性是由一些质数的萌元素乘积构成（例如，猫耳的值是2，弱气的值是3，黄毛的值是5，病娇的值是7，双马尾的值是11等等）

举个例子，正妹是双份的猫耳，而且有一份弱气，她的属性值为223=12。

现在组员关心一个问题，希望知道离自己最近且有相同萌元素上司是谁，例如，属性值为2、4、6、45这样的属性值都算是和正妹有相同的属性。

然而，组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。

输入格式 第一行，n,k 表示成员数与询问的次数

第二行，n个数，分别是1~n号成员的属性值

接下来n-1行，x_i,y_i 表示x_i是y_i的上司。

接下来来k行，有两种情况

1 u_i 询问离u_i成员最近且有相同萌元素上司。

2 u_i a 更改u_i的属性值为a

输出格式

对于每个1类型的询问，输出符合要求的编号。如果没有符合要求的编号，输出-1。

输入输出样例 输入 #1

4 6 10 8 4 3 1 2 2 3 3 4 1 1 1 2 1 3 1 4 2 1 9 1 4

输出 #1复制

-1 1 2 -1 1

---

解题思路：若 gcd(u,fa[u]) >0 则拥有同样的萌元素 例如： gcd(3,12)=3>0 12=223 gcd(6,18)=6>0 6=23 18=23*3

---

#include<bits/stdc++.h> using namespace std; const int N=200005; int n,k,x,y,t; int a[N],fa[N]; int solve(int u){//暴力搜索u的父亲节点 for(int v=fa[u];v;v=fa[v]){ if(__gcd(a[u],a[v])>1) return v; } return -1; } int main() { cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n-1;i++) { cin>>x>>y; fa[y]=x; } while(k--) { cin>>t; if(t==1){ cin>>x; cout<<solve(x)<<endl;; }else{ cin>>x>>y; a[x]=y; } } return 0; }

洛谷P1029 最大公约数和最小公倍数问题

题目描述 输入两个正整数 x0,y0，求出满足下列条件的 P,Q 的个数：

1.P,Q 是正整数。

2.要求 P,Q 以 x0为最大公约数，以 y0为最小公倍数。

试求：满足条件的所有可能的 P,Q 的个数。

输入格式 一行两个正整数 x0，y0

输出格式 一行一个数，表示求出满足条件的 P, Q的个数。

输入输出样例 输入 #1

3 60

输出 #1

4

---

最大公约数和最小公倍数的乘积就是原两个数的积 枚举一个数，判断它能否被读入的两个数的积整除，如果可以再判断它和两个数的积除以它所得的数的最大公约数和读入的最大公约数是否相同，如果相同则ans++

#include<bits/stdc++.h> using namespace std; int m,n,ans; int main(){ cin>>m>>n; if(m==n)ans--; n*=m;//先把两数相乘，再遍历他的因子即可 for(int i=1;i<=sqrt(n);i++) { if(n%i==0&&__gcd(i,n/i)==m) ans+=2; } cout<<ans; return 0; }

伯特兰-切比雪夫定理

伯特兰—切比雪夫定理说明： 若整数n > 3，则至少存在一个质数p，符合n < p < 2n − 2。 另一个稍弱说法是：对于所有大于1的整数n，至少存在一个质数p，符合n < p < 2n。

洛谷P5535 【XR-3】小道消息

题目描述 小 X 想探究小道消息传播的速度有多快，于是他做了一个社会实验。

有 n 个人，其中第 i 个人的衣服上有一个数i+1。小 X 发现了一个规律：当一个衣服上的数为 i 的人在某一天知道了一条信息，他会在第二天把这条信息告诉衣服上的数为 j 的人，其中gcd(i,j)=1（即i,j 的最大公约数为 1）。在第 0 天，小 X 把一条小道消息告诉了第 k 个人，小 X 想知道第几天时所有人都会知道这条小道消息。

可以证明，一定存在所有人都知道了这条小道消息的那一天。

提示：你可能需要用到的定理——伯特兰-切比雪夫定理。

输入格式 一行 2 个正整数 n,k。

数据范围：

2≤n≤10^14 1≤k≤n。 输出格式 一行一个正整数，表示答案。

输入输出样例 输入 #1

3 1

输出 #1

2

输入 #2

6 4

输出 #2

1

分两种情况：n为质数或者合数 质数： 1.当n/2 < k < n 且k为质数时可得只需要1次就可以完成任务，因为没有数是它的倍数，由于它自身是质数，所以它必然与所有小于n的数互质 2.当k <= n/2 且k为质数时,由于有数为它的倍数，显然不互质，所以不可能一次完成，由于伯特兰-切比雪夫定理可知，一定有一个质数n< p< 2n，两个质数一定互质，所以最后又回到了第一种情况，所以一共需要 2 次。 合数: 对于一个合数，显然一开始不与所有数互质，由伯特兰-切比雪夫定理可知一定有 n/2 < p <n p为质数,显然这个合数不是p的倍数，与p互质，这是第一步，然后再由质数的第一种情况得出一共需要 2次。

#include<bits/stdc++.h> #define ll long long using namespace std; ll n,k; bool prime(ll x) { for (ll i=2;i<=sqrt(x);i++) if (x%i==0) return false; return true; } int main() { cin>>n>>k; if (prime(k+1)) { if ((n+1)/(k+1)==1) puts("1"); else puts("2"); } else puts("2"); }

线性同余方程&乘法逆元

简单的同余运算

同余公式也有许多我们常见的定律,比如相等律,结合律,交换律,传递律….如下面的表示:

** 1)a≡a(mod d) 2)a≡b(mod d)→b≡a(mod d) 3)(a≡b(mod d),b≡c(mod d))→a≡c(mod d)

如果a≡x(mod d),b≡m(mod d),则 4)a+b≡x+m （mod d） 5)a-b≡x-m (mod d) 6)ab≡xm (mod d ) 7）a≡b（mod d）则a-b整除d **

裴蜀定理

luoguP4549 裴蜀定理

题目描述

贝祖定理可以推广到n个,n>=2 ax+by+cz+…=k if(k%gcd(a,b,c,…)==0) 该式子有整数解 else 没有整数解 在此题中： ax+by+cz+……=gcd(a,b,c……）

#include<bits/stdc++.h> using namespace std; const int N=25; int n,ans; int main() { cin>>n; while(n--) { int t; cin>>t; if(t>0) ans=__gcd(ans,t); else ans=__gcd(ans,-t); } cout<<ans; } ## luoguP3811 乘法逆元  ```cpp #include<cstdio> #define ll long long using namespace std; const int maxn=3e6+5; ll inv[maxn]={0,1}; int main(){ int n,p; scanf("%d%d",&n,&p); printf("1\n"); for(int i=2;i<=n;i++) inv[i]=(ll)p-(p/i)*inv[p%i]%p,printf("%d\n",inv[i]); return 0; }

输入格式 第一行一个整数n，表示序列元素个数。

第二行 n 个整数，表示序列 A。

输出格式 一行一个整数，表示 S>0 的前提下 S 的最小值。

输入输出样例 输入 #1 2 4059 -1782 输出 #1 99

---

## 求乘法逆元 ### 拓展欧几里得  ```cpp void Exgcd(ll a, ll b, ll &x, ll &y) { if (!b) x = 1, y = 0; else Exgcd(b, a % b, y, x), y -= a / b * x; } int main() { ll x, y; Exgcd (a, p, x, y); x = (x % p + p) % p; printf ("%d\n", x); //x是a在mod p下的逆元 }

快速幂

ll fpm(ll x, ll power, ll mod) { x %= mod; ll ans = 1; for (; power; power >>= 1, (x *= x) %= mod) if(power & 1) (ans *= x) %= mod; return ans; } int main() { ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元 }

线性算法

inv[1] = 1; for(int i = 2; i < p; ++ i) inv[i] = (p - p / i) * inv[p % i] % p;

阶乘逆元 O(n)求

luoguP3951 小凯的疑惑

#include <cstdio> #include <iostream> using namespace std; long long int a, b; int main() { scanf("%lld%lld", &a, &b); printf("%lld\n", a * b - a - b); return 0; }

中国剩余定理

来源

洛谷P3868 [TJOI2009]猜数字【中国剩余定理】

扩展中国剩余定理

特别的：m1,m2,m3 … 不互质

lt exgcd(lt a,lt b,lt &x,lt &y) { if(b==0){x=1;y=0;return a;} lt gcd=exgcd(b,a%b,x,y); lt tp=x; x=y; y=tp-a/b*y; return gcd; } lt excrt() { lt x,y,k; lt M=bi[1],ans=ai[1];//第一个方程的解特判 for(int i=2;i<=n;i++) { lt a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b) lt gcd=exgcd(a,b,x,y),bg=b/gcd; if(c%gcd!=0) return -1; //判断是否无解 x=mul(x,c/gcd,bg); ans+=x*M;//更新前k个方程组的答案 M*=bg;//M为前k个m的lcm ans=(ans%M+M)%M; } return (ans%M+M)%M; }

P4777 【模板】扩展中国剩余定理（EXCRT） 题解

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10; ll bi[N],ai[N]; int n; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0){x=1;y=0;return a;} ll gcd=exgcd(b,a%b,x,y); ll tp=x; x=y; y=tp-a/b*y; return gcd; } ll mul(ll a,ll b,ll mod) { ll res=0; while(b>0) { if(b&1) res=(res+a)%mod; a=(a+a)%mod; b>>=1; } return res; } ll excrt() { ll x,y; ll M=bi[1],ans=ai[1];//第一个方程的解特判 for(int i=2;i<=n;i++) { ll a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b) ll gcd=exgcd(a,b,x,y),bg=b/gcd; if(c%gcd!=0) return -1; //判断是否无解 x=mul(x,c/gcd,bg); ans+=x*M;//更新前k个方程组的答案 M*=bg;//M为前k个m的lcm ans=(ans%M+M)%M; } return (ans%M+M)%M; } int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>bi[i]>>ai[i]; } cout<<excrt()<<endl; return 0; }