#1027889 (C++23) No.2979 直角三角形の個数

• 問題: No.2979 直角三角形の個数
• ユーザー: 👑 testestest
• 提出日時: 2024-11-21 21:47:23
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,448 ms / 4,000 ms
• コード長: 917 bytes
• コンパイル時間: 3,280 ms
• コンパイル使用メモリ: 249,748 KB
• 実行使用メモリ: 7,296 KB
• 最終ジャッジ日時: 2024-12-02 23:30:09
• 合計ジャッジ時間: 8,418 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	4 ms; 5,248 KB
testcase_15	AC	4 ms; 5,248 KB
testcase_16	AC	8 ms; 5,248 KB
testcase_17	AC	16 ms; 5,248 KB
testcase_18	AC	42 ms; 5,248 KB
testcase_19	AC	56 ms; 5,248 KB
testcase_20	AC	152 ms; 5,248 KB
testcase_21	AC	227 ms; 5,248 KB
testcase_22	AC	1,168 ms; 6,784 KB
testcase_23	AC	1,201 ms; 6,912 KB
testcase_24	AC	2 ms; 5,248 KB
testcase_25	AC	2 ms; 5,248 KB
testcase_26	AC	2 ms; 5,248 KB
testcase_27	AC	3 ms; 5,248 KB
testcase_28	AC	1,448 ms; 7,296 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;
using i64=long long;

int main(){
	i64 N;
	cin >> N;
	i64 sqrtN=sqrt(N)+3;
	vector<bool>prime(sqrtN,true);
	vector<int>mu(sqrtN,1);
	for(i64 i=2;i<sqrtN;i++)if(prime[i]){
		mu[i]*=-1;
		for(i64 j=2*i;j<sqrtN;j+=i)prime[j]=false,mu[j]*=-1;
		for(i64 j=i*i;j<sqrtN;j+=i*i)mu[j]=0;
	}

	auto f=[&](i64 n){
		//return Σ_{x,y} n/(2(x+y)(2x+y))
		if(n<12)return 0LL;
		i64 ans=0;
		i64 V=cbrt(n);
		i64 B=n/V;
		i64 X=(sqrt(4*B+1)-3)/4;
		for(i64 x=1;x<=X;x++){
			i64 Y=(sqrt(x*x+2*B)-3*x)/2;
			for(i64 y=1;y<=Y;y++)ans+=n/(2*(x+y)*(2*x+y));
		}
		vector<i64>cnt(V+1);
		for(i64 i=1;i<=V;i++){
			i64 U=n/i;
			i64 X=(sqrt(4*U+1)-3)/4;
			for(i64 x=1;x<=X;x++)cnt[i]+=(i64)((sqrt(x*x+2*U)-3*x)/2);
		}
		for(i64 i=1;i<V;i++)ans+=i*(cnt[i]-cnt[i+1]);
		return ans;
	};

	i64 ans=0;
	for(i64 i=1;12*i*i<=N;i+=2)if(mu[i])ans+=mu[i]*(f(N/i/i)-f(N/2/i/i));
	cout << ans << endl;
}