#1029692 (C++17(gcc12)) No.2979 直角三角形の個数

• 問題: No.2979 直角三角形の個数
• ユーザー: ecottea
• 提出日時: 2024-12-03 00:33:50
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2,634 ms / 4,000 ms
• コード長: 1,678 bytes
• コンパイル時間: 2,330 ms
• コンパイル使用メモリ: 206,404 KB
• 実行使用メモリ: 7,296 KB
• 最終ジャッジ日時: 2024-12-03 00:34:02
• 合計ジャッジ時間: 11,566 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
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	1 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	3 ms; 5,248 KB
testcase_14	AC	5 ms; 5,248 KB
testcase_15	AC	6 ms; 5,248 KB
testcase_16	AC	12 ms; 5,248 KB
testcase_17	AC	27 ms; 5,248 KB
testcase_18	AC	73 ms; 5,248 KB
testcase_19	AC	98 ms; 5,248 KB
testcase_20	AC	268 ms; 5,248 KB
testcase_21	AC	408 ms; 5,248 KB
testcase_22	AC	2,154 ms; 6,656 KB
testcase_23	AC	2,208 ms; 6,912 KB
testcase_24	AC	2 ms; 5,248 KB
testcase_25	AC	2 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB
testcase_27	AC	3 ms; 5,248 KB
testcase_28	AC	2,634 ms; 7,296 KB

ソースコード

// https://wandbox.org/permlink/Y56SQ7EPYsvoEv13
// を見つけたけどこれでいいの？ → 3RE，そう単純じゃないらしい

// sqrt → sqrtl, cbrt → cbrtl にしてみた

// 配列サイズをちょっと大きくしてみた

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

ll solve(ll N){
	ll sqrtlN=sqrtl(N)+3;
	vector<bool>prime(sqrtlN+10,true);
	vector<int>mu(sqrtlN+10,1);
	rep(i,2,sqrtlN+5)if(prime[i]){
		mu[i]*=-1;
		for(ll j=2*i;j<=sqrtlN;j+=i)prime[j]=false,mu[j]*=-1;
		for(ll j=i*i;j<=sqrtlN;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=cbrtl(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=(sqrtl(4*B+1)-3)/4;
		for(ll x=1;x<=X;x++){
			ll Y=(sqrtl(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+10); // 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+sqrtl(x*x+2*U) / 2
			//for(ll x=1;2*(x+1)*(2*x+1)<=U;x++)cnt[i]+=(ll)((sqrtl(x*x+2*U)-3*x)/2);
			ll X=(sqrtl(4*U+1)-3)/4;
			for(ll x=1;x<=X;x++)cnt[i]+=(ll)((sqrtl(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;
}