1.来个小定理（上次DP的青蛙过河用过）
事实上，假如他们的gcd！=1,那么P,q都可以表示成gcd的倍数，因此假如一个数不是gcd的倍数就不可以表示，若互质由裴蜀定理大于一定时一定可以表示出。
事实上为（p-1)(q-1)-1.(p,q互质）
2.
模拟+单链表式并查集：
p[i]表示单链表的下一个节点，i所在树的根节点为从i开始向右找第一个没有被用的位置。
一开始都是自环，假如后面2被用过，那么2连3，假如1用了，1连2，这样子通过路径压缩就可以高效的实现。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1100010;
int p[N];
int find(int x){
if(p[x]==x) return x;
return p[x]=find(p[x]);
}
int main(){
int n;
cin>>n;
for(int i=1;i<N;i++) p[i]=i;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
x=find(x);
printf("%d ",x);
p[x]=x+1;
}
}3.组合数问题求最值-背包：
我们令f[i][j][k]表示从前i个数选j个，总和余数为k的选法集合的max
易得状态转移方程：
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][（(k-ai)%K+K）%K]),但是复杂度太大了。
同时，我们可以得到一个结论，对于余数相同的，我们只要保证存最大值前3就可以了，这样复杂度就可以了
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,f[4][N];
vector<int> a[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
a[x%m].push_back(x);
}
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=0;i<m;i++){
sort(a[i].begin(),a[i].end());
reverse(a[i].begin(),a[i].end());
for(int u=0;u<3&&u<a[i].size();u++){
int x=a[i][u];
for(int j=3;j>=1;j--){
for(int k=0;k<m;k++){
f[j][k]=max(f[j][k],f[j-1][(k-x%m+m)%m]+x);
}
}
}
}
cout<<f[3][0];
}4.数学
恶心到了，直接放图：
下面是矩阵快速幂以及龟速乘的代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p;
LL qmul(LL a,LL b){
LL res=0;
while(b){
if(b&1) res=(res+a)%p;
a=(a+a)%p;
b>=1;
}
return res;
}
LL t[2][2];
void mul(LL c[][2],LL a[][2],LL b[][2]){
memset(t,0,sizeof(t));
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
t[i][j]=(t[i][j]+qmul(a[i][k],b[k][j]))%p;
}
}
}
memcpy(c,t,sizeof(t));
}
LL F(LL n){
if(!n) return 0;
LL f[2][2]={1,1};
LL a[2][2]={{0,1},{1,1}};
for(LL k=n-1;k;k>=1){
if(k&1) mul(f,f,a);
mul(a,a,a);
}
return f[0][0];
}
