SRM567Div2

Mid:
SSR(A,B) = (√A,√B)^2
という関数があって、1<=A<=N,1<=B<=Mを満たす整数A,B組み合わせの中でSSR(A,B)が整数となるものの数を求める。
本番で解けなかった。

SSR(A,B) = (√A,√B)^2 = A^2 + B^2 + 2*√(AB)
より、√(AB)の値が整数なら条件を満たす。

例えばA=2に固定した時
√2 * √2、
√2 * √8、
√2 * √18なども整数になり条件を満たす。
なのでこのような数は全部√2として扱う。

√の中に平方数を残さない（中学でやる簡単化?）よう処理をしてあげた後、
√の中が同じ物の組み同士を計算。

割と愚直にやっても計算が間に合ってしまう。

#include <vector>
#include <iostream>
using namespace std;
class TheSquareRootDilemma {
public:
    int div(int N)
    {
      for(int i=2; i*i<=N; ++i)
      {
        while(N%(i*i)==0)
        {
          N /= (i*i);
        }
      }
      return N;
    }

    int countPairs(int N, int M) {
      vector<int> A(80000,0),B(80000,0);
      for(int i=1; i<=N; ++i) A[div(i)]++;
      for(int i=1; i<=M; ++i) B[div(i)]++;

      int res=0;
      for(int i=1; i<80000; ++i)
        res += A[i]*B[i];
      return res;
    }
};