문제 풀이

에라토스테네스의 체로 먼저 소수리스트를 만들고, 그 소수들을 모두 조합해서 소수끼리 더해서 만들 수 있는 수, 소수끼리 곱해서 만들 수 있는 수인지 아닌지의 여부를 check배열과 check2배열에 각각 저장을한다.

그리고 재귀를 통해서 숫자를 만들어 주고 그 숫자가 문제의 조건에 부합하는지 확인해주면 된다.
조건 2번에 나누어 떨어진다는다는 의미를 오해를해서 좀 오래 걸렸다.
105를 5로 나눈다면 나머지가 0일때 까지만 나누면된다. 105 / 5 = 21이고 21 / 5 는 나머지가 1로 나누어 떨어지지 않는다.

문제 링크

boj/22943

소스코드

PS/22943.java

 
    import java.io.*;
    import java.lang.reflect.Array;
    import java.util.*;

    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        static ArrayList<Long> primeList = new ArrayList<Long>();
        static int []check = new int[100001];
        static int []check2 = new int[100001];
        static int []visit = new int[10];
        static int k,m;
        static int ans ;
        public static void main(String[] args) throws IOException {
            StringTokenizer st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());
             m = Integer.parseInt(st.nextToken());

            boolean []prime= new boolean[100001];

            Arrays.fill(prime,true);
            prime[0] = false;
            prime[1] = false;
            for(int i=2;i*i<100000;i++)
            {
                if(prime[i]) {
                    for (int j = i*i;j<=100000;j+=i)
                    prime[j] = false;
                }
            }
            for(int i=0;i<100000;i++)
            {
                if(prime[i])
                    primeList.add((long) i);
            }
          for(int i=0;i<primeList.size();i++)
          {
              for(int j=i+1;j<primeList.size();j++)
              {
                  if(primeList.get(i) + primeList.get(j) < 100000)
                  check[(int)(primeList.get(i) + primeList.get(j))] =1;
              }
          }

            for(int i=0;i<primeList.size();i++)
            {
                for(int j=i;j<primeList.size();j++)
                {

                    if((long)(primeList.get(i) * primeList.get(j)) < 100000)
                        check2[(int) (primeList.get(i) * primeList.get(j))] =1;
                }
            }
            int ret = comb(0,0,k,0);
            bw.write(Integer.toString(ret));
            bw.flush();
        }
        static boolean check2(int val)
        {
            while(val %m ==0)
                val/=m;

           if(check2[val] == 1)
               return true;
            return false;
        }

        static int comb(int cur,int idx , int max,int val)
        {
            if(idx == max)
            {
                if(check[val] == 1&& check2(val))
                    return 1;
                return 0;
            }
            int ret = 0;
            for(int i = cur ;i<=9;i++)
            {
                if(idx ==0 && i == 0)
                    continue;
                if(visit[i] == 1)
                    continue;
                visit[i] =1 ;
                ret += comb(cur ,idx+1,max,val*10 + i);
                visit[i] = 0;
            }
            return ret;
        }

    }