Hatena::Grouptopcoder

thorikawa@top coder

topcoder id: the_poly
 | 

2013-02-19

TopCoder - SRM567 Div1

| 18:04 | はてなブックマーク - TopCoder - SRM567 Div1 - thorikawa@top coder

250 TheSquareRootDilemma

一見して簡単そうだが、計算量減らすのが思ったより難しかった。式を展開すると、ijが平方数になる1<=i<=N,1<=j<=Mのペア数を計算すればよい。総当りは計算量O(N*M)で間に合わないが、ペアのうち片方をiで固定して考えると、i*a=平方数となる最小のaを求めてやれば、あとは、a*平方数がペアのもう片方になり、これは計算量O(N*log(M))で求められる。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

typedef long long ll;

class TheSquareRootDilemma {
public:
int countPairs(int n, int m) {
  int res=0;
  for(ll i=1; i<=n; i++){
    ll tmp = i;
    ll smallest = 1;
    for(ll j=2; j*j<=i; j++){
      int e = 0;
      while((tmp > 1) && (tmp%j==0)){
        e++;
        tmp /= j;
      }
      if(e%2) smallest *= j;
    }
    smallest *= tmp;
    for(ll j=1; j*j*smallest<=m; j++){
      res++;
    }
  }
  return res;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/thorikawa/20130219
 |