KTLT13. Mô đun m

Tiêu đề: KTLT13. Mô đun m Thu May 12, 2022 8:07 pm

KTLT13. Mô đun m
Cho n số nguyên a1, a2, . . ., an (|ai| < 109, 0 ≤ n ≤ 100 000). Hãy xác định dãy con nhiều phần tử nhất từ dãy đã cho, sao cho không có hai phần tử nào của dãy con có tổng chia hết cho m (2 ≤ m ≤ 100 000).
Dữ liệu: Vào từ file văn bản MODM.INP:
• Dòng thứ nhất chứa 2 số nguyên n và m,
• Dòng thứ 2 chứa n số nguyên a1, a2, . . ., an .
Kết quả: Đưa ra file văn bản MODM.OUT:
• Dòng thứ nhất chứa số nguyên k – số phần tử của dãy con tìm được,
• Dòng thứ 2 chứa k số nguyên – chỉ số trong dãy ban đầu của các phần tử thuộc dãy con.
Nếu có nhiều kết quả thì đưa ra một trong số chúng.
Ví dụ:
MODM.INP
3 2
1 100 10
MODM.OUT
2
1 2

Tổng số bài gửi : 16 Join date : 10/05/2022

Code:: #include<bits/stdc++.h>
using namespace std;
#define forl(i,a,b) for (int i=a; i<=b; i++)
#define forr(i,a,b) for (int i=a; i>=b; i--)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

int n,A[100001],b[100001],c[100001],m,a[1000001],res,id[1000001];
void nhap()
{
cin >> n >> m;
forl (i,1,n) cin >> a[i];
}

void sinh(int i)
{
forl(j,0,1)
{
A[i] = j;
if (i == n-1)
{
int dem = 0;
for(int i=0;i<n;i++)
{
if(A[i] == 1)
{
b[++dem] = a[i + 1];
id[dem] = i + 1;
}

}
for(int i1 =1; i1 <= n - 1; i1++)
{
for(int j1 = i + 1; j1 <= n; j1++)
if((b[i1] + b[j1]) % m == 0) return;
if(dem > res)
{
res = max(res,dem);
for(int i2 = 1; i2<= res; i2++) c[i2] = id[i2];
}

}

}
else sinh(i+1);

}
}
int main ()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
nhap();
sinh(0);
cout<<res<<endl;
for(int i = 1; i <= res; i++) cout<<c[i]<<" ";
return 0;
}