#include<cstdio>#include<map>#include<queue>#include<cstring>#include<iostream>#include<algorithm>#include<vector>#include<list>#include<set>#include<cmath>using namespace std;const int maxn = 1e5 + 5;const int INF = 1e9;const double eps = 1e-6;typedef unsigned long long ULL;typedef long long LL;typedef pair<int, int> P;#define fi first#define se secondstruct Edge { int from, to, cap, flow;};struct Dinic { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void ClearAll(int n) { for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void ClearFlow() { for(int i = 0; i < edges.size(); i++) edges[i].flow = 0; } void AddEdge(int from, int to, int cap) { edges.push_back((Edge){from, to, cap, 0}); edges.push_back((Edge){to, from, 0, 0}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; while(BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; }};Dinic g;int a[maxn];map<LL, int> M;int main(){ int n, m; while(scanf("%d%d", &n, &m) != EOF){ for(int i = 1;i <= n;i++){ cin >> a[i]; a[i] %= m; } int source = 0, sink = n*n+1; g.ClearAll(n*n+5); for(int i = 1;i <= n;i++) g.AddEdge(source, i, 1); M.clear(); int cnt = n+1; for(int i = 1;i <= n;i++){ LL now = a[i]; map<LL, int> vis; vis.clear(); int num = 0; while(1){ vis[now] = 1; if(M.count(now)==0){ g.AddEdge(cnt, sink, 1); M[now] = cnt++; } g.AddEdge(i, M[now], 1); now = (now*a[i])%m; num++; if(num > n || vis.count(now)) break; } } cout << g.Maxflow(source, sink) << endl; } return 0;}
