106 - Fermat vs. Pythagoras

106 – Fermat vs. Pythagoras

這一題是給一個數字N：
1. 找出所有小於等於N的正整數中，互質的畢式組數(如: (3, 4, 5)是一組互質的畢式組數)數量。
2. 找出所有小於等於N的正整數中，不能構成畢式組數(不需是互質的畢式組數)的數字數量。

乍看之下只要用brute force找出所有的畢式數對即可，但由於N最大值是1,000,000，光要建立小於1,000,000的質數表就已經超過3秒鐘的Time Limit，所以一定要找其他方法。

參考Algorithmist，才發現使用畢式定理的通解，處理時間會大大的縮短。

X^2 + Y^2 = Z^2
( r^2 - s^2 )^2 + ( 2rs )^2 = ( r^2 + s^2 )^2

由於Z=(r^2+s^2)，要找出 Z<N 即是 (r^2+s^2)<N，因此r, s < N^(1/2)，搜尋數量縮減到根號N，也就是最大1000！

而互質且一奇一偶的(r, s)，可以產生所有互質的畢式組數。在乘上倍數後便可以找出其他非互質的畢式組數了。

TIPS

記錄數字是否為畢式組數的陣列要用char型別，int型別無法開到1,000,000

CODE

#include <stdio.h>

int p, prime[200];

void findprime(void);
int rp(int a, int b);

int main(){
  int i, j;
  int n, r, s, rsq, ssq, rpt;
  char num[1000002]="";
  
  /*Find all prime numbers between 1 and 1000*/
  findprime();
  
  while( scanf("%d", &n) != EOF ){
    rpt = 0;
    
    for(r=2; (rsq = r*r)<n; r++){
      for(s=1; s<r && (rsq+(ssq = s*s)<=n); s++){
        if( ((r%2 == 1) ^ (s%2 == 1)) && (rp(r,s) == 1) ){
          rpt++;
          
          /*time the triple pair*/
          for(i=1; (i*(rsq+ssq))<=n; i++)
            num[ i*(rsq - ssq) ] = num[ i*(2*r*s) ] = num[ i*(rsq + ssq) ] = 1;
        }/*(r, s) pair can generate relatively prime triple*/
      }/*s*/
    }/*r*/
    
    printf("%d ", rpt);
    j = 0;
    for(i=1; i<=n; i++){
      if( num[i] == 1 )
        num[i] = 0;
      else
        j++;
    }
    printf("%d\n", j);
  }/*while input data*/

  exit(0);
}

void findprime(void){
  int i, j, tmp[1001];
  
  for(i=2; i<1001; i++)
    tmp[i] = 1;
  
  p = 0;
  for(i=2; i<1001; i++){
    if( tmp[i] == 1 ){
      prime[p] = i;
      p++;
      
      for(j=(i+i); j<1001; j+=i)
        tmp[j] = 0;
    }
  }
}

int rp(int a, int b){
  int i;
  
  for(i=0; i<p && prime[i]<a ; i++)
    if( (a % prime[i] == 0) && (b % prime[i] == 0) )
      return 0;
  
  return 1;
}