PKU Judge Online 1218 THE DRUNK JAILER

■1218 THE DRUNK JAILER

□Problem
ある刑務所には部屋がn個(1,2,3,…,n)ある．
ある夜，退屈していた看守は，ゲームを始めた．
1.各部屋(1,2,3,…)の鍵を開けていく．
2.1つ飛ばしに各部屋(2,4,6,…)の鍵を閉めていく．
3.2つ飛ばしに各部屋(3,6,9,…)の鍵を開けていく．
…
n.n-1つ飛ばしに各部屋(nのみ)の鍵を開けていく．
最終的に，鍵が空いている部屋はいくつあるか．

□Solution
やるだけ．

□Code

view plainprint?

1. package p1218;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.       
10.     void run(){  
11.         for(int t=sc.nextInt();t>0;t--){  
12.             int n=sc.nextInt();  
13.             int[] a=new int[n];  
14.             // 0-lock  
15.             // 1-unlock  
16.             for(int k=1;k<=n;k++)  
17.                 for(int i=k-1;i<n;i+=k)  
18.                     a[i]=1-a[i];  
19.             int ans=0;  
20.             for(int e:a)  
21.                 ans+=e;  
22.             println(""+ans);  
23.         }  
24.     }  
25.       
26.     void println(String s){  
27.         System.out.println(s);  
28.     }  
29.   
30.     void print(String s){  
31.         System.out.print(s);  
32.     }  
33.   
34.     public static void main(String[] args){  
35.         new Main().run();  
36.     }  
37. }  

package p1218;

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{
    Scanner sc=new Scanner(System.in);
    
    void run(){
        for(int t=sc.nextInt();t>0;t--){
            int n=sc.nextInt();
            int[] a=new int[n];
            // 0-lock
            // 1-unlock
            for(int k=1;k<=n;k++)
                for(int i=k-1;i<n;i+=k)
                    a[i]=1-a[i];
            int ans=0;
            for(int e:a)
                ans+=e;
            println(""+ans);
        }
    }
    
    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }

    public static void main(String[] args){
        new Main().run();
    }
}