PKU 1218. THE DRUNK JAILER. AC

문이 홀수번 열리고 닫히면 되니 약수의 개수가 홀수개인 제곱수의 개수를 찾아 출력합니다.

 

#include <stdio.h> #include <math.h> int is_square(int n) { int a, b, count=1; switch(n%10) { case 2: case 3: case 7: case 8: return 0; break; } for(a=2, b=0; (n&1)==0; n>>=1, b++); count*=(b+1); for(a=3; n>1; a+=2) { for(b=0; n%a==0; n/=a, b++); count*=(b+1); } return (count&1); } int run(int n) { int i, count=0; for(i=1; i<=n; i++) if(is_square(i)) count++; return count; } int main() { int line, n; scanf("%d", &line); while(line--) { scanf("%d", &n); printf("%d\n", run(n)); } return 0; }