글 읽기 - 정수 게임 문제 해결 좀 도와주세요ㅜㅜ (시뮬레이션 안돌렸습니다)

Rose 5년 전 0

일단 주어진 배열의 수들을 모두 정렬해놓고, 어떤수가 그 앞 인덱스의 수(배열 안의 더 작은 수) 로 나누어지면 없앱니다.왜냐하면 어차피 없애질 수이기 때문입니다.
그리고 이제 남아있는 수들의 조합을 구합니다. (1개, 2개,---n개까지)
구한 조합에 들어있는 모든 수들의 최소공배수를 유클리드 호제법 으로 구해줍니다.
그리고 수의 개수에따라 만약 홀수개라면 (n/최소공배수)를 더해주고, 짝수개라면 (n/최소공배수)를빼줍니다. 왜냐하면 중복되는 수를 카운트하기 위하여 그렇게 하는데, 조합개수가 하나인수는 n개중에서 어떤수의 배수이고, 2개는 두수의 최소공배수인데, 그전에 하나를 지울때 중복으로 지워진것을 카운트하기 위함입니다. 그렇게 해서1개 조합에서 n개조합까지 이전과 같은 방식으로 빼거나 더해줍니다.
그렇게하면 지워지는 수의 개수가 구해지는데, 이제 그 값을 n에서 빼줍니다.

분명히 로직이 어딘가 잘못되어서 틀린 것 같은데 틀린곳 지적해주시면 정말 감사하겠습니다..

#include <stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int data[20];
vector<int> dat,uclid(20);
int uc(int a,int b){
	if(b==0)return a;
	return uc(b,a%b);
}
int realsum,n;
void process(int q){
	int sum=1;
    for(int i = q-1; i>= 0; i--){
            //printf("%d ", uclid[i]);
            sum=(uclid[i]*sum)/uc(uclid[i],sum);
    }

    if(q%2==0) realsum-=(n/sum);
    else realsum+=(n/sum);
    //printf("%d %d %d %d\n",q,sum,n/sum,realsum);
    //printf("\n");
}
//n개의 숫자 중 r개를 선택하는 조합
void Comb(int n, int r, int q){
    if(r == 0){
        process(q);
        return;
    }else if(n<r){
        return;
    }
    else {  //loop이 아님
        uclid[r-1] = dat[n-1];
        Comb(n-1, r-1, q);  //n-1Cr-1: 현재 수를 선택한 경우
        Comb(n-1, r, q);    //n-1Cr: 현재 수를 선택하지 않은 경우
    }
}

int main(){
	int m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d",&data[i]);
	}
	sort(data,data+m);
	for(int i=0;i<m;i++){
		if(data[i]==0)continue;
		for(int j=i+1;j<m;j++){
			if(data[j]==0)continue;
			if(data[j]%data[i]==0){
				data[j]=0;
			}
		}
		dat.push_back(data[i]);
	}
	for(int i=1;i<=dat.size();i++){
		Comb(dat.size(), i, i);
	}

	printf("%d",n-realsum);
    return 0;
}

chogahui05 5년 전 1

int로 커버되는 범위인가요?

chogahui05 5년 전 1

아.. 저도 잘못 풀었네요.

회 먹고 와서 뚝배기 깨 봅니다.

Rose 5년 전 0

회맛있게드세요

갔다와서 저좀알려주세요 ㅜㅜ

Rose 5년 전 0

헐미쳤따 unsigned long long 으로 바꾸니까 바로통과되네요 감사합니다.

댓글을 작성하려면 로그인해야 합니다.