yukicoder : No.1514 Squared Matching

これは典型かな。
https://yukicoder.me/problems/no/1514

問題

正整数Nが与えられる。
1以上N以下の整数対(a,b)のうちa*bが平方数になるものは何通りか。

解法

1～Nの整数を平方数で割れるだけ割り、その結果が等しいものの数の二乗和を数えよう。
Nが大きいので、できるだけ掛け算割り算の頻度を減らそう。

int N;
int num[50000001];
int dp[50000001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) num[i]=i;
	for(i=2;i*i<=N;i++) {
		for(j=i*i;j<=N;j+=i*i) while(num[j]%(i*i)==0) num[j]/=i*i;
	}
	for(i=1;i<=N;i++) dp[num[i]]++;
	
	
	ll ret=0;
	FOR(i,N+1) if(dp[i]) ret+=1LL*dp[i]*dp[i];
	cout<<ret<<endl;
}

まとめ

Nが10^7以上の問題、言語によっては配列確保に苦労しそう。