読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 106 : Fermat vs. Pythagoras

問題リンク;Fermat vs. Pythagoras

問題概要:
あるpositive integer Nが与えられる
x,y,zをN以下のpositive integersとする
x*x + y*y = z*z を満たす様なx,y,zの組の内、x,y,zのそれぞれが互いに素なものの数と、x*x+y*y = z*z を満たすようなx,y,zでないN以下の数字の数を数えよ

解法:
Pythagorean triple - Wikipedia, the free encyclopedia
上記のサイトで使われている式を利用して高速化した
x = k * (m*m - n*n)
y = k * (2*m*n)
z = k * (m*m+n*n)

これを利用する亊で、
mはsqrt(N)まで、nは(m*m+n*n) <= N以下である時だけみれば良くなる

x*x+y*y=z*zにでてこない数を記録するときはsetなどを使うとTLEするので
配列に記録すること
それぞれが互いに素かどうかはそれぞれの最大公約数が1になっているかで判定

コード:

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

using namespace std;
typedef long long ll;

void compute(ll N)
{
  int cnt = 0;
  int lim = sqrt(N);
  bool total[N+1];
  rep(i,N+1)total[i] = false;

  for(int n=1 ; n<=lim; n++)
    {
      for(int m=n+1;(n*n+m*m)<=N;m++)
	{
	  int a = m*m - n*n;
	  int b = 2*m*n;
	  int c = m*m + n*n;
	  if(a > b)swap(a,b);
	  if(b > c)swap(b,c);
	  if(c > N)continue;

	  total[a] = total[b] = total[c] = true;

	  if(__gcd(a,b) == 1 && __gcd(b,c) == 1 && __gcd(a,c) == 1)
	    cnt++;

	  ll k = 2; 
	  while(k*c <= N)
	    {
	      total[k*a] = total[k*b] = total[k*c] = true;
	      k++;
	    }
	}
    }

  int rest = 0;
  rep(i,N+1)rest += total[i];

  cout << cnt << " " << N - rest << endl;
}

int main()
{
  ll N;
  while(cin >> N)
    {
      compute(N);
    }
  return 0;
}