COLOCON -Colopl programming contest 2018- C - すぬけそだて――ごはん――
解法
A~Bまでの整数が書かれた各カードを購入するか購入しないで全探索する。
制約等から時間計算量がO(2^35)と思ってしまうが
「...これまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカードを食べたとき...」というこの問題の特徴を考えると
2で割り切れる整数は2枚以上購入できない、3で割り切れる整数は2枚以上購入できない、5で...(省略)
という感じで時間計算量O(2^35)も掛からない。
「2で割り切れる整数は2枚以上購入できない」ということで、全探索中に購入出来るカードは高々18枚しかない。
これを3で割り切れる,5で割り切れる,...という風に考えると十分全探索で間に合うと考えられる。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; public class Main { long A,B; long[] prev; private long gcd(long x,long y) { return y == 0 ? x : gcd(y,x % y); } // 整数A~整数Bの各整数に対して 購入する/しない で探索 private int dfs(long n,int it) { if (n == B + 1) { return 1; } // 整数nを購入しない場合 int ret = dfs(n + 1,it); // 購入済みの各整数と整数nが互いに素であるかをチェック boolean ok = true; for(int i = 0;i < it;i++) { if (gcd(n,prev[i]) != 1) { ok = false; } } // 整数nを購入する場合 if (ok) { prev[it] = n; ret += dfs(n + 1,it + 1); } return ret; } private void solve() { A = nextLong(); B = nextLong(); prev = new long[(int)(B - A + 1)]; int it = 0; out.println(dfs(A,it)); } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }