简单来说，题中要求三维 LIS.
考虑如何使用 CDQ 分治.
我们可以事先将坐标按 $x$ 轴排序，先递归处理左边，再考虑左边对右边的影响.
由于我们再处理该段区间之前已经将该区间按照 $x$ 坐标排序，我们便能保证右区间的 $x$ 坐标一定不小于左区间的 $x$ 坐标.
这样有什么好处呢 ？
这不就可以将一个 3 维的问题转成 2 维的问题了吗 ？
由于我们只需考虑左区间对右区间的影响，我们无需考虑 $x$ 坐标所带来的困扰.
想象一下二维问题怎么做 ？
对右区间和左区间分别按照 $y$ 坐标为第一关键字， $z$ 坐标按照第二关键字排序，利用双指针分别扫描左右区间.
设两个指针分别为 $tl$ 和 $tr$.
我们分这两种情况来讨论.
1. $arr[tl].y<=arr[tr].y$
这时由于左面的比右面小，说明左面的还可能出现比右面小的情况，就不急着查询，而且左面该点还会对右面产生影响.
所以，我们利用左面的更新右面，并 $++tl$.
2. $arr[tl].y>arr[tr].y$
左面的大于右面的，则右面该点在以后也不可能再被左面所贡献，直接查询即可，并 $++tr$.
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 500060
#define ll long long
#define nex (oo = (oo * A) % mod)
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,cnt,fin,ans[maxn];
long long mod,oo = 1,A,H[maxn];
void getmax(int &a,int b){ if(b>a) a = b; }
struct Node{
long long x,y,z;
int id;
}node[maxn],arr[maxn];
int cmpx(Node a,Node b){ return(a.x==b.x&&a.y==b.y)? (a.z < b.z) : ((a.x==b.x)?a.y<b.y:a.x<b.x); }
int cmpy(Node a,Node b) {
if(a.y==b.y) return a.z<b.z;
return a.y<b.y;
}
int equal(Node a,Node b) { return (a.x==b.x&&a.y==b.y&&a.z==b.z); }
struct BIT{
int C[maxn];
int lowbit(int x){ return x & (-x); }
void update(int p,int x) {
while(p < maxn) {
C[p] = max(C[p],x);
p += lowbit(p);
}
}
int query(int p) {
if(p<=0) return 0;
int ss=0;
while(p>0) {
ss=max(ss,C[p]),p-=lowbit(p);
}
return ss;
}
void del(int p) {
while(p < maxn) C[p] = 0,p+=lowbit(p);
}
}tree;
void solve(int l,int r){
if(l >= r) return;
int mid = (l + r) >> 1,tl = l,tr = mid+1;
solve(l,mid);
sort(arr + l,arr + mid + 1,cmpy),sort(arr + mid + 1,arr + r + 1,cmpy);
while(tl<=mid&&tr<=r) {
if(arr[tl].y<arr[tr].y) {
tree.update(arr[tl].z,ans[arr[tl].id]);
++tl;
}
else {
getmax(ans[arr[tr].id],tree.query(arr[tr].z-1)+1);
++tr;
}
}
for(int i = tr;i<=r;++i) getmax(ans[arr[i].id],tree.query(arr[i].z-1)+1);
for(int i = l;i<=mid;++i) tree.del(arr[i].z);
sort(arr+mid+1,arr+1+r,cmpx),solve(mid+1,r);
}
int main(){
//setIO("input");
scanf("%lld%lld%d",&A,&mod,&n);
for(int i = 1;i <= n; ++i){
oo = (oo * A) % mod,node[i].x = oo;
oo = (oo * A) % mod,node[i].y = oo;
oo = (oo * A) % mod,node[i].z = oo;
if(node[i].x > node[i].y) swap(node[i].x,node[i].y);
if(node[i].x > node[i].z) swap(node[i].x,node[i].z);
if(node[i].y > node[i].z) swap(node[i].y,node[i].z);
}
node[0].x = node[0].y = node[0].z = -333333333;
sort(node + 1,node + 1 + n,cmpx);
for(int i = 1;i <= n; ++i)
if(!equal(node[i],node[i-1])) arr[++cnt] = node[i],arr[cnt].id = cnt;
//=================================================================================
//对 x 离散
for(int i = 1;i <= cnt; ++i) H[i] = arr[i].x;
sort(H+1,H+1+cnt);
for(int i = 1;i <= cnt; ++i) arr[i].x = lower_bound(H + 1,H + 1 + cnt,arr[i].x)-H;
//对 y 离散
for(int i = 1;i <= cnt; ++i) H[i] = arr[i].y;
sort(H+1,H+1+cnt);
for(int i = 1;i <= cnt; ++i) arr[i].y = lower_bound(H + 1,H + 1 + cnt,arr[i].y)-H;
//对 z 离散
for(int i = 1;i <= cnt; ++i) H[i] = arr[i].z;
sort(H + 1,H + 1 + cnt);
for(int i = 1;i <= cnt; ++i) arr[i].z = lower_bound(H + 1,H + 1 + cnt,arr[i].z)-H;
//=================================================================================
for(int i = 1;i <= cnt; ++i) ans[arr[i].id] = 1;
solve(1,cnt);
for(int i = 1;i <= cnt; ++i) fin = max(fin,ans[arr[i].id]);
printf("%d",fin);
return 0;
}