Round 1B

199位でRound 2に通過。

A

格子点上の点がn個与えられた時に重心が格子点にのるような異なる3点の取り方の数を出せという問題。とりあえずsmallに関してO(n^3)のコードを書いて通しておく。よくよく考えるとx,yに関しての3で割った余りのみ見ればいいことがわかった。

B

L=[A...B](A <= B , n=B-A <= 10^6)のリスト上の数をP以上の共通の素数をもつものは同じ集合に入れるというルールで併合していったときに互いに素な集合は何個できるかという問題。
集合の併合をUnionFindをもちいてO(1)で(本当はO(1)ではないけど)やればO(n log n)で解ける。
ただケース数が多かったのと素数判定をさぼってたせいで8分以内に終わらなかった。まじめに素数判定をしたら1分で解が求まるようになった。

C

Largeの解法がわからなかった。とりあえずsmallだけだした。

以下A,Bのプログラム

import java.util.Scanner;
public class A {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for(int i = 1 ; i <= N ; i++){
      int n = sc.nextInt();
      long A = sc.nextLong();
      long B = sc.nextLong();
      long C = sc.nextLong();
      long D = sc.nextLong();
      long X = sc.nextLong();
      long Y = sc.nextLong();
      long M = sc.nextLong();
      long mod[][] = new long[3][3];
      mod[(int)(X % 3)][(int)(Y % 3)]++;
      for(int j = 1 ; j < n ; j++){
        X = (A * X + B) % M;
        Y = (C * Y + D) % M;
        mod[(int)(X % 3)][(int)(Y % 3)]++;
      }
      long count = 0;
      for(int m0 = 0 ; m0 < 9 ; m0++){
        for(int m1 = m0 ; m1 < 9 ; m1++){
          for(int m2 = m1 ; m2 < 9 ; m2++){
            int x0 = m0 / 3;
            int y0 = m0 % 3;
            int x1 = m1 / 3;
            int y1 = m1 % 3;
            int x2 = m2 / 3;
            int y2 = m2 % 3;
            if((x0 + x1 + x2) % 3 == 0 && (y0 + y1 + y2) % 3 == 0){
              long add = mod[x0][y0] * mod[x1][y1] * mod[x2][y2];
              if(m0 == m1 && m1 == m2){
                long m = mod[x0][y0];
                add = (m * (m - 1) * (m - 2)) / 6;
              }else if(m0 == m1){
                long m = mod[x0][y0];
                add = ((m * (m - 1)) / 2) * mod[x2][y2];
              }else if(m1 == m2){
                long m = mod[x1][y1];                
                add = ((m * (m - 1)) / 2) * mod[x0][y0];
              }
              count += add;
            }
          }
        }
      }
      System.out.printf("Case #%d: %d\n" , i , count);
    }
  }
}

import java.util.*;

class UnionFind{
  int p[];
  int rank[];
  public UnionFind(int n){
    p = new int[n];
    for(int i = 0 ; i < n ; i++)
      p[i] = i;
    rank = new int[n];    
  }
  void union(int x , int y){
    link(find(x) , find(y));
  }
  void link(int x , int y){
    if(x == y)return ;
    if(rank[x] > rank[y]){
      p[y] = x;
    }else{
      p[x] = y;
      if(rank[x] == rank[y]){
        rank[y]++;
      }
    }
  }
  
  int find(int x){
    if(x != p[x]){
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

public class B {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int C = sc.nextInt();
    boolean ps[] = new boolean[1000001];
    Arrays.fill(ps, true);
    ps[0] = ps[1] = false;
    for(int i = 2 ; i < ps.length ; i++){
      if(!ps[i])continue;
      for(int j = i + i ; j < ps.length ; j += i){
        ps[j] = false;
      }
    }
    for(int i = 1 ; i <= C ; i++){
      long A = sc.nextLong();
      long B = sc.nextLong();
      long P = sc.nextLong();
      int n = (int)(B - A + 1);
      UnionFind uf = new UnionFind(n);
      long arr[] = new long[n];
      for(int j = 0 ; j < n ; j++){
        arr[j] = A + j;
      }
      for(long p = P ; p < n ; p++){
        if(!ps[(int)p])continue;
        long start = p * (A / p);
        if(start < A){
          start += p;
        }
        int a = (int)(start - A);
        for(long u = start + p ; u <= B ; u += p){
          int b = (int)(u - A);
          uf.union(a, b);
        }
      }
      Set<Integer> set = new HashSet<Integer>();
      for(int j = 0 ; j < n ; j++){
        set.add(uf.find(j));
      }
      System.out.printf("Case #%d: %d\n" , i , set.size());
    }
  }
}