結果

問題 No.2979 直角三角形の個数
ユーザー ecotteaecottea
提出日時 2024-12-03 00:04:39
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,921 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 205,944 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-12-03 00:04:47
合計ジャッジ時間 8,633 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 3 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 RE -
testcase_11 AC 2 ms
5,248 KB
testcase_12 RE -
testcase_13 AC 3 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 RE -
testcase_18 AC 44 ms
5,248 KB
testcase_19 AC 58 ms
5,248 KB
testcase_20 AC 155 ms
5,248 KB
testcase_21 AC 260 ms
5,248 KB
testcase_22 AC 1,196 ms
6,656 KB
testcase_23 AC 1,223 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,494 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://wandbox.org/permlink/Y56SQ7EPYsvoEv13
// を見つけたけどこれでいいの？

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

ll naive(ll N){
	ll ans=0;
	rep(i,1,N){
		if(4*i*i>N)break;
		for(ll j=i+1;2*j*j+2*i*j<=N;j+=2)if(__gcd(i,j)==1)ans+=N/(2*j*j+2*i*j);
	}
	return ans;
}

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

	auto f=[&](ll n){
		//return Σ_{x,y} n/(2(x+y)(2x+y))
		if(n<12)return 0LL;
		// 分母がn^(2/3)以上かどうかで計算方法を変える
		ll ans=0;
		ll V=cbrt(n); // n/hoge がV未満になるものは別に数える
		ll B=n/V;  // hoge<=B ⇔ n/hoge>=V
		//for(ll x=1;2*(x+1)*(2*x+1)<=B;x++)for(ll y=1;2*(x+y)*(2*x+y)<=B;y++)ans+=n/(2*(x+y)*(2*x+y));
		ll X=(sqrt(4*B+1)-3)/4;
		for(ll x=1;x<=X;x++){
			ll Y=(sqrt(x*x+2*B)-3*x)/2;
			for(ll y=1;y<=Y;y++)ans+=n/(2*(x+y)*(2*x+y));
		}
		// i<=n/hoge ⇔ hoge<=n/i
		vector<ll>cnt(V+1); // cnt[i] は n/hoge>=i となる(x,y)の個数
		rep(i,1,V+1){
			ll U=n/i;
			// 2*(x+y)*(2*x+y)<=U  ⇔  y=-3x+sqrt(x*x+2*U) / 2
			//for(ll x=1;2*(x+1)*(2*x+1)<=U;x++)cnt[i]+=(ll)((sqrt(x*x+2*U)-3*x)/2);
			ll X=(sqrt(4*U+1)-3)/4;
			for(ll x=1;x<=X;x++)cnt[i]+=(ll)((sqrt(x*x+2*U)-3*x)/2);
		}
		rep(i,1,V)ans+=i*(cnt[i]-cnt[i+1]);
		return ans;
	};

	ll ans=0;
	for(ll i=1;i*i<=N;i+=2)if(mu[i])ans+=mu[i]*(f(N/i/i)-f(N/2/i/i));
	return ans;
}

int main(){
ll n;
cin >> n;

cout << solve(n) << endl;

return 0;

	rep(e,2,7+1){
		ll n=pow(10,e);
		cout << n << ' ' << solve(n) << ' ' << naive(n) << endl;
	}

	cout << endl;

	rep(e,9,13+1){
		ll n=pow(10,e);
		clock_t start=clock();
		cout << n << ' ' << solve(n) << ' ' << (double)(clock()-start)/CLOCKS_PER_SEC << endl;
	}
}
0