SRM567-div2-med-500

(sqrt(A)+sqrt(B))^2が整数になるABの組み合わせの数を調べる

1<=A<=N
1<=B<=M

1<=N,M<=77777

#include<iostream>
#include<queue>
#include<cmath>
#include<utility>
#include<vector>
#include<string>
#include<cstdio>
using namespace std;

class TheSquareRootDilemma{
public:
	int countPairs(int n, int m){
		int ans=0;
		bool sq[80000]={0};
		for(int i=2;i*i<80000;i++){
			for(int k=1;k*i*i<80000;k++){
				sq[k*i*i]=1;
			}
		}
		for(int i=1;i*i<n+1;i++){
			for(int j=1;j*j<m+1;j++){
				for(int k=1;(i*i*k<=n)&&(j*j*k<=m);k++){
					if(sq[k]!=1||k==1){
						cout<<i*i*k<<" "<<j*j*k<<endl;
						ans++;
					}
				}
			}
		}
		return ans;
	}
};

解答

N,Mの数が大きいので全探索だとTLEします

条件を整理するとABが平方数の時となる

A,Bが平方数と共通因数を持つ数の時に
ABが平方数となるので
A=i*i*k B=j*j*k
で数え上げます

kが平方数を因数に持つときに
i*iと平方数部分がかぶってしまうので
その部分は除去します