[伯俊]#1241髪の毛パチパチ

10563 ワード
白駿 algorithm テキストリンク

質問する


厳智の誕生日を記念して、学生たちはパーティーを開いている.親指はN(1≦N≦100000)名の学生に順番に1からNまで番号をつけて、順番に囲んで座らせます.(すなわち、i番目の学生はi−1とi+1の間に座っている.しかし、n番目の学生はn−1番目の学生と最初の学生の間に座っている.)
N人の学生が座って「パチパチ頭」ゲームをしようとした.ゲームのルールは以下の通りです.学生1人につき自分の頭に10万以下の自然数の1つを使う.そして1番からN番まで生徒が一人ずつ立ち上がって回り、自分が書いた数字が他人が書いた数字の倍数であれば、その生徒の頭をパチパチと叩く.
問題は、学生一人一人が起きて自分の位置に戻る前に、全部で何人かの学生の頭を打つことです.

入力


1行目は生徒数Nを入力し、次の行は1からNを入力し、各生徒が自分の頭に書いた数字を入力する.

しゅつりょく


全部でN行あり、1行目は1人目の学生が1周して頭を打つ学生数を出力する.

入力例1

5
2
1
2
3
4

サンプル出力1

2
0
2
1
3

に答える


この問題は学生たちが書いた数とその数で、それから学生たちの周りを回って、その学生が書いた数の総数を合わせて答えを求めます.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] cnt = new int[1000001];   //수 세기위한 배열
        int[] ans = new int[N];

        for(int i=0; i<N; i++) {
            int x = arr[i] = Integer.parseInt(br.readLine()); //학생들이 쓴 수 저장
            cnt[x]++;   //학생들이 쓴 수 갯수 세기
        }

        for(int i=0; i<N; i++) {
            int temp = arr[i];

            for (int k=1; k*k <= temp; k++) {   //각 학생이 쓴 수의 약수 구하기
                if (temp % k == 0) {
                    ans[i] += cnt[k];
                    if (k*k < temp) {       //약수 쌍의 갯수를 더해줌
                        ans[i] += cnt[temp/k];
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++)
            sb.append(ans[i]-1).append("\n");   //자기 자신도 계산하기 때문에 -1씩

        System.out.print(sb);
    }
}
05章式と文
#3.再学習したCSSを整理する