Sinh tổ hợp
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(n\) số tự nhiên \({1,2,3,4, ..., n}\). Tổ hợp chập \(k\) của \(n\) số này là một cách chọn ra \(k\) số khác nhau trong \(n\) số, không kể thứ tự (tức là: chọn \([1,2,3]\) cũng giống như chọn \([3,2,1], [2,3,1], [1,3,2], ...\)).
Cho biết trước \(n,k\). Em hãy in ra tất cả tổ hợp chập \(k\) của \(n\) theo thứ tự từ điển.
Nhắc lại, hai dãy số \(s,t\) có cùng độ dài \(k, s\) có thứ tự từ điển bé hơn \(t\) khi tồn tại duy nhất \(i (1 \le i \le k)\)
- \(s[j] = t[j]\) với mọi \(1 \le j < i\)
- \(s[i] < t[i]\)
Nói cách khác, \(s < t\) khi tại vị trí \(i\) đầu tiên mà \(s[i] \neq t[i]\), ta có \(s[i] < t[i]\).
Trong tất cả các tổ hợp (cách chọn), có bao nhiêu cách mà tích của các số được chọn là một số chính phương?
Input
- Một dòng duy nhất chứa hai số \(n,k (1 \le k \le n \le 16)\)
Output
- In ra các tổ hợp, mỗi cách trên một dòng
- Ở dòng cuối cùng, in ra số lượng tích là số chính phương
Example
Test 1
Input
5 3 Output
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
0
Bình luận
//--------------------------------
// ** ** * ** * * *
// * * * * * * * * * *
// * * * * * * * ******
// * * * * * * * *
// * * * * ** * *
//--------------------------------
include <bits/stdc++.h>
using namespace std;
define ll long long
//tim kiem nhi phan
int timkiemnhiphan(int a[],int n,int x){
int l=1;
int r=n;
while(l<=r){
int mid=(r+l)/2;
if(x==a[mid]) return mid;
else if(x<a[mid]) r=mid-1;
else l=mid+1;
}
return -1;
}
//sort so dau
bool cmp(pair<int,int> a, pair<int,int> b){
if (a.first != b.first) {
return a.first < b.first;
}
return a.second < b.second;
}
// dao nguoc so
int reverseNum(int n){
int res=0;
while(n>0){
res=res*10+n%10;
n=n/10;
}
return res;
}
//kiem tra so nguyen to
int isprimeNum(int n){
if(n<2) return false;
if(n==2 || n==3) return true;
if(n%2==0) return false;
for(int i=3;i*i<=n;i+=2){
if(n%i==0) return false;
}
return true;
}
//tong uoc
long long sumgcd(long long n){
long long sumgcd1=0;
for(long long i=1;i*i<=n;i++){
if(n%i==0){
sumgcd1+=i;
if(i!=n/i) sumgcd1+=n/i;
}
}
return sumgcd1;
}
//dem cac uoc
long long countgcd(long long n){
long long cnt=0;
for(long long i=1;i*i<=n;i++){
if(n%i==0){
cnt++;
if(i!=n/i) cnt++;
}
}
return cnt;
}
//tong cac uoc nguyen to
long long countgcdprime(long long n){
int cnt=0;
for(int i=2;i<=n;i++){
while(n%i==0){
cnt++;
n=n/i;
}
}
return cnt;
}
define android ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
long long d[1000001];
long long sumgcdfake[10000001];
int c[1001],b[1001];
int main() {
android
}
2 bình luận nữa