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; }