テキトーなメモ帳

テキトーなメモ帳

AOJ:0590 Available Areas

まず、与式を式変形して、xの式とyの式を出すと(Aは面積)、
2*x*y+x+y=Aより

xの式は
x*(2*y+1)+y=A
x=(A-y)/(2*y+1)


yの式は
y*(2*x+1)+x=A
y=(A-x)/(2*x+1)


よって、部屋の面積が正しいかどうか見るためには
yの式を使って(A-x)%(2*x+1)==0(もしくはxの式を使って(A-y)%(2*y+1)==0)が成り立つかどうかを見ればいい。


このとき、yの式を使うとして、探索範囲を1<=x<=Aとすると計算時間がかかるので、探索範囲を絞ることを考える。
場合分けによって、A=2*x*y+x+yという与式を式変形すれば探索範囲をどう狭めたらいいかわかる。


x<=y
のとき
A=2*x*y+x+y
x<=yより、両辺にxをかけて
x*x<=x*y
また、x<=yより、両辺にxを足して
2*x<=x+y

よって
A=2*x*y+x+y>=2*x*x+x+y>=2*x*x+2*x>=x*x


x>=y
のとき
A=2*x*y+x+y
x>=yより、両辺にyをかけて
x*y>=y*y
また、x>=yより、両辺にyを足して
x+y>=2*y

よって
A=2*x*y+x+y>=2*y*y+x+y>=2*y*y+2*y>=y*y


以上から
x<=yのときはyの式を使って探索範囲を1<=x && 2*x*x+2*x<=A
x>=yのときはxの式を使って探索範囲を1<=y && 2*y*y+2*y<=A
とすれば、計算量が減らせるとわかる。
(他の方の解答を読むと、探索範囲を1<=x && x*x<=Aと1<=y && y*y<=Aにしている人もいた。)


xの式・yの式は変数名が変わっただけで、A(面積)の値が一緒なら結果も一緒になるので、
片方の式だけ使えば十分である。

#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;

static const double EPS = 1e-8;

static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

bool is_valid(int area){
  for(int x=1;2*x*x+2*x<=area;x++){
    if((area - x) % (2*x + 1) == 0) return true;
  }
  return false;
}

int main(){
  int n;
  while(~scanf("%d",&n)){
    int res = 0;
    for(int i=0;i<n;i++){
      int area;
      scanf("%d",&area);
      if(!is_valid(area)) res++;
    }
    printf("%d\n",res);
  }
}