글 읽기 - 서로소의 개수 문제 어느부분이 틀렸는지 잘 모르겠습니다.

smu201111192 6년 전 1

gcd는 순서가 상관없기에 현재원소를 뽑는경우와 뽑지 않는경우를 생각하면서

결국 끝에 도달했을때 여태까지 뽑은 원소들의 gcd가 1인지를 판단하면서

재귀로 풀어봤는데 wa를 받았습니다. 어느부분이 잘못 됬는지 잘 모르겠습니다. ㅠㅠ

#include <iostream>
#include <cstring>
using namespace std;
int dp[101][100000];
int arr[100001];
int mod=10000003;
int n;
int getGcd(int a,int b){
    if(b>a)swap(a,b);
    if(b==0)return a;
    return getGcd(b,a%b);
}
int go(int pos,int gcd){
    int &ans=dp[pos][gcd];
    if(pos==n+1){
        if(gcd==1)return 1;
        else return 0;
    }
    if(ans!=-1)return ans;
    int a,b;
    if(gcd==0){  //아직 아무것도 집합에 추가안한상태
        a=go(pos+1,arr[pos]);
        b=go(pos+1,0);
    }
    else{
        a=go(pos+1,getGcd(gcd,arr[pos]));  //pos번째 원소를 뽑음
        b=go(pos+1,gcd);  //pos번째 원소를 뽑지 않음
    }
    ans=(a%mod+b%mod)%mod;
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    cout<<go(1,0);
    return 0;
}

zych1751 6년 전 1

dp 배열을 [101][100001] 로 고쳐주세요

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

문제

문제

출처

ICPC

서로소의 개수 문제 어느부분이 틀렸는지 잘 모르겠습니다.

smu201111192 6년 전 1

zych1751 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말